[백준] 2669 직사각형 네개의 합집합의 면적 구하기(Python) - Simulation

📌 문제

평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭짓점이 겹칠 수도 있다.

이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오.

 

입력

입력은 네 줄이며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어진다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭짓점의 x좌표, y좌표이고 세 번째와 네 번째의 정수는 사각형의 오른쪽 위 꼭짓점의 x좌표, y좌표이다. 모든 x좌표와 y좌표는 1이상이고 100이하인 정수이다.

출력

첫 줄에 네개의 직사각형이 차지하는 면적을 출력한다.

예제 입력

1 2 4 4
2 3 5 7
3 1 6 5
7 3 8 6

예제 출력

26

---

📌 풀이

Code

import sys
input = sys.stdin.readline

visited = [[0]*101 for _ in range(101)]     # 방문 배열
cnt = 0                                     # 면적 내 사각형 개수
for _ in range(4):                          # 입력은 4줄
    c1, r1, c2, r2 = map(int, input().split())
    for r in range(r1, r2):
        for c in range(c1, c2):
            if not visited[r][c]:           # 방문한적 없으면
                visited[r][c] = 1           # 방문 표시
                cnt += 1                    # 사각형 1개 카운트
print(cnt)

 

Solution

1. 101 X 101 크기의 방문 배열 만들기

 

2. 주어진 입력 좌표가 이루는 사각형 내 점들을 모두 방문 표시, 표시 횟수 만큼 카운트 증가

(방문하지 않은 점에 대해서만)

• 점의 선택 방식: 내부 작은 사각형의 좌상단 꼭짓점 좌표가 해당 사각형을 대표하는 좌표라고 생각

 

3. 최종적으로 나온 카운트 개수 출력

• 최종적으로 나온 카운트 개수는 곧 전체 영역 내 작은 사각형의 개수가 됨
• 작은 사각형의 개수를 1이라고 했을 때, 작은 사각형의 개수 = 전체 직사각형이 차지하는 면적

---

깨달은 점

방문 리스트는 DFS 배울 때 처음 사용해봤는데, 이렇게 다른 방면에서 사용해볼 수 있어서 뿌듯했습니다!

점점 두뇌가 유연해지는 느낌이랄까요~