2583번: 영역 구하기 / silver 1 / DFS

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

2583번: 영역 구하기

'''
2583번: 영역 구하기 / silver 1 / DFS
'''
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**8)


# x,y ~ a,b 꼭짓점 직사각형 graph에 넣는 함수
def put_square(y, x, b, a):
    for i in range(x, a):
        for j in range(y, b):
            graph[i][j] = 2


# graph에 연속된 빈 공간 찾고 넓이 리턴하는 함수
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def dfs(x, y):
    global cnt
    graph[x][y] = 3
    cnt += 1
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if 0 <= nx < N and 0 <= ny < M:
            if graph[nx][ny] == 0:
                dfs(nx, ny)


# 입력받기
N, M, K = map(int, input().split())
square = []
for _ in range(K):
    square.append(list(map(int, input().split())))
# N*M 그래프 만들기
graph = [[0 for _ in range(M)] for _ in range(N)]
# 그래프에 K 영역 대입하기
for i in range(K):
    x, y, a, b = square[i]
    put_square(x, y, a, b)
# 빈 공간 체크
empty_space = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            cnt = 0
            dfs(i, j)
            empty_space.append(cnt)
# 출력하기
empty_space.sort()
print(len(empty_space))
for v in empty_space:
    print(v, end=' ')

코드 리뷰

- 해당 문제를 푸는데 약 50분 소요되었고, 정답 판정을 받았습니다.

- 그래프에 K 영역을 어떻게 대입할지 고민하는데에 30분 이상 소요했습니다.

 

생각해야 할 부분

[그래프에 K 영역 대입하기]

- 문제에서의 K영역 좌표와, 리스트에서의 좌표가 다르다는 점

   - 문제에서는 왼쪽밑 (0,0) / 리스트는 왼쪽위 (0,0)

   해결방안

   - (1) 행과 열을 바꾸기 (x, y, a, b) => (y, x, b, a) 

   - (2) 직사각형 넣을 시, 기존 문제 예제와는 상하 대칭 되게 넣기

       - 문제의 예제와 같이 직사각형을 넣으려면 x좌표를 수정해야 합니다.

       - 하지만, x좌표를 모두 수정을 하지 않으면 상하대칭일 것이라 판단했습니다.

 

[그래프에 빈 공간 찾기]

- K 영역을 그래프에 모두 넣었으면, 이제 문제에서 요구하는 빈 공간을 체크해야 합니다.

- 빈 공간을 찾기 위해 DFS를 활용했습니다.