[백준/Python] 2583번 : 영역 구하기

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

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

 

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

문제 코드

from collections import deque
m, n, k = map(int, input().split())
board = [[0] * n for _ in range(m)]

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

visited = [[0] * n for _ in range(m)]
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
answer = []

def bfs(x, y):
    q = deque([(x,y)])
    res = 1
    visited[x][y] = 1
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            
            if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 0 and not visited[nx][ny]:
                res += 1
                visited[nx][ny] = 1
                q.append((nx, ny))
    answer.append(res)
    
for i in range(m):
    for j in range(n):
        if board[i][j] == 0 and visited[i][j] == 0:
            bfs(i, j)

print(len(answer))
answer.sort()
print(*answer)

 

문제 풀이

1. 입력 받기 (문제에서는 0,0이 좌측 하단부터 시작인 점을 감안하여 배열 설정)

2. 너비 우선 탐색을 사용

2-1. 전체 보드판에서 비어있는 칸을 기점으로 bfs 실행 (전체 보드판 실행)

2-2. 비어있는 칸의 개수를 셈과 동시에 방문 여부도 체크, 최종적으로 큐가 비어있으면 그 루프의 최종 칸 크기를 answer리스트에 저장

3. 최종적으로 나온 answer의 길이와 정렬된 answer를 출력