BOJ 2583번 - 영역 구하기

[백준 온라인 저지 링크]

2583번: 영역 구하기

입력이 약간 마음에 들지 않는 문제였습니다!

첫째 줄에서 M, N을 입력받아 무의식적으로 M = 행, N = 열인줄 알았지만, 실제 풀이에서는 N = 행, M = 열로 바꿔 풀어야 했네요 ㅡㅡ!

이외에는 2667번 단지번호붙이기, 1012번 유기농 배추 등의 문제와 동일한 방법으로 해결할 수 있는 문제였습니다.

 

[정답 코드 - Python]

from collections import deque

M, N, K = map(int, input().split())
board = [[0] * N for i in range(M)]
visited = [[False] * N for i in range(M)]
size_list = []
cnt = 0

for i in range(K):
    dx, dy, ux, uy = map(int, input().split())
    for row in range(dy, uy):
        for col in range(dx, ux):
            board[row][col] = 1

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def BFS(start_node):
    global cnt
    cnt += 1
    size = 1
    q = deque()
    q.append(start_node)
    while q:
        y, x = q.popleft()
        visited[y][x] = True
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < M and 0 <= nx < N:
                if visited[ny][nx] == False and board[ny][nx] == 0:
                    q.append((ny, nx))
                    visited[ny][nx] = True
                    size += 1

    size_list.append(size)


for row in range(M):
    for col in range(N):
        if board[row][col] == 0 and visited[row][col] == False:
            BFS((row, col))

size_list.sort()

print(cnt)
print(*size_list)