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

💡문제

백준 2583번 문제 링크

🍀풀이

코드

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

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

graph = [[0] * m for _ in range(n)]

result = []

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 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):
            graph[i][j] = 2

def bfs(x, y):
    graph[x][y] = 1
    queue = deque()
    queue.append([x, y])
    num = 1
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = 1
                queue.append([nx, ny])
                num += 1
    return num

count = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            result.append(bfs(i, j))
            count += 1
print(count)
print(*sorted(result))

문제를 처음 봤을 때, 어떤식으로 풀어야할까 고민을 하다가 처음에 k개의 직사각형을 bfs 돌려서 넓이를 구하고 전체 넓이에서 빼면 되나? 생각을 했는데 그럼 개수는 어떻게 구하지 하는 생각을 했다...
근데 생각 해보니 직사각형 좌표들을 따로 빼고 바깥 영역들에 대해서 bfs를 돌려서 개수와 넓이를 구하면 되겠다 하는 생각을 했다. (진짜 빡세네) 구하는 식은 그림(백준문제)에서 한거처럼 했고, 넓이는 배열에 넣어서 정렬해서 출력하는 식으로 했다.

다른 사람들 코드를 보는데 보통 다들 dfs로 풀더라구... 나도 다음에 dfs로 다시 풀어봐야겠다