[백준 2583번] 영역 구하기

from collections import deque

m,n,k = map(int,input().split())

area = [[0]*n for _ in range(m)]
visited = [[False]*n for _ in range(m)]

count_list = []

for i in range(k):
    x1, y1, x2, y2 = map(int,input().split())
    
    for j in range(y1,y2):
        for k in range(x1,x2):
            area[j][k] = 1

def bfs(x,y):

    if visited[x][y] or area[x][y] == 1:
        return False
    
    count = 1
    
    queue = deque([(x,y)])
    visited[x][y] = True
    
    while queue:

        v = queue.popleft()
        
        nx = [-1,1,0,0]
        ny = [0,0,-1,1]
        
        for i in range(4):
            temp_x = v[0] + nx[i]
            temp_y = v[1] + ny[i]

            if temp_x >= 0 and temp_x < m and temp_y >=0 and temp_y < n:
                if area[temp_x][temp_y] == 0 and not visited[temp_x][temp_y]:
                    count += 1
                    visited[temp_x][temp_y] = True
                    queue.append((temp_x,temp_y))
        
    count_list.append(count)
    
    return True

for i in range(m):
    for j in range(n):
        bfs(i,j)

count_list.sort()

print(len(count_list))
for i in count_list:
    print(i,end=" ")

이번 문제는 m x n 크기의 영역에 직사각형의 좌표(왼쪽 아래, 오른쪽 위)를 사용하여 직사각형을 그린 후, 직사각형을 제외한 영역 중 분리된 영역의 개수와 넓이를 구하는 문제이다.

 

따라서 먼저 직사각형의 좌표를 사용하여 인접 행렬 방식으로 선언된 영역(area)에 직사각형이 그려진 영역을 별도의 값(1)으로 표시하고, DFS나 BFS를 활용하여 영역의 개수를 구하여 풀이하였다.

 

본인은 BFS를 복습할 겸 BFS를 활용하여 풀었는데, 2차원 리스트에서의 탐색 알고리즘을 복습해볼 수 있었던 좋은 문제였다 :)