[Python/파이썬] - 백준(BOJ) 2583번 : 영역 구하기

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

2583번: 영역 구하기

 

 

간단한 BFS를 이용하는 문제입니다.

 

arr 배열에 영역의 정보를 저장하고 이미 탐색한 지역인지를 확인하는 visit 배열을 만듭니다.

이후 arr 전체 탐색을 하며 arr[i][j] == 0인 경우 queue에 넣은 뒤 visit을 1로 하고 s값을 0으로 세팅합니다.

BFS로 탐색하여 arr 정보가 0이고 visit 정보가 0인 경우 queue에 추가하고 visit을 1로 합니다.

queue에서 popleft 할 때마다 s값을 1씩 증가시키며 queue가 빌 때까지 반복합니다.

queue가 비면 answer 배열에 s 값을 추가하고 arr 다음값 탐색을 반복합니다.

 

모든 탐색이 끝나면 answer를 출력합니다.

 

 

 

import sys
from collections import deque
input = sys.stdin.readline

m, n, k = map(int,input().split())
arr = [[0 for _ in range(n)] for _ in range(m)]
dy = [0,-1,0,1]
dx = [1,0,-1,0]
for _ in range(k):
    x1, y1, x2, y2 = map(int,input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            arr[i][j] = 1
queue = deque([])
answer = []
for i in range(m):
    for j in range(n):
        if arr[i][j] == 0:
            queue.append([i, j])
            arr[i][j] = 1
            s = 0
            while queue:
                y, x = queue.popleft()
                s += 1
                for k in range(4):
                    yy = y + dy[k]
                    xx = x + dx[k]
                    if 0 <= yy < m and 0 <= xx < n and arr[yy][xx] == 0:
                        queue.append([yy, xx])
                        arr[yy][xx] = 1
            answer.append(s)
print(len(answer))
print(*sorted(answer),sep=' ')