[백준] 2669번: 직사각형 네개의 합집합의 면적 구하기 - 파이썬/python

https://www.acmicpc.net/problem/2669

2669번: 직사각형 네개의 합집합의 면적 구하기

접근 방식

- 중복 영역에 대한 처리 방식 고민

 

코드 풀이

grid = [[0]*100 for _ in range(100)]

for _ in range(4):
    a, b, c, d = map(int, input().split())
    for i in range(a, c):
        for j in range(b, d):
            grid[i-1][j-1] = 1
            
cnt = 0 # 색칠된 grid 영역 count
for k in range(100):
    cnt += sum(grid[k])
print(cnt)

직사각형 4개를 그릴 때 중복 영역에 대해서 직접 코드상으로 처리해준다면 3, 4개의 사각형이 동시에 겹치는 경우 처리가 매우 어려워질 수 있습니다. 따라서 범위 영역에 대해 grid를 설정하여 색칠해주는 방식으로 진행했습니다. (1로 처리하므로, 이미 처리되어 있어 중복 처리되더라도 값이 변하지 않습니다.)

이때 주의해야 할 점은 왼쪽 하단 좌표는 grid에 1 처리해주지만, 오른쪽 상단 좌표는 grid에 1처리하지 않는 것입니다. 즉 범위 내 좌표가 영역의 좌하단에 위치할때만 grid에 1을 처리하는 것입니다 (a<= i < c, b<= j < d)

 

메모

- 이중 list 구문은 sum(list) 처리로 원소의 합을 구할 수 없습니다. 세부 리스트의 sum값을 더해주는 방식으로 접근해줘야 합니다.