[백준/파이썬] 2583번

📍백준 2583번 문제

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

코드

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

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


def bfs(a, b):
    visited[a][b] = True
    graph[a][b] = 1
    cnt = 1
    que = deque()
    que.append((a, b))
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < m and 0 <= ny < n and visited[nx][ny] == False:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = True
                    graph[nx][ny] = graph[x][y] + 1
                    que.append((nx, ny))
                    cnt += 1
    return cnt


# m: 높이 n: 가로
m, n, k = map(int, input().split())
graph = [[0 for _ in range(n)]for _ in range(m)]
visited = [[False for _ in range(n)]for _ in range(m)]
res = []
cnt = 0
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    x2 -= 1
    y2 -= 1
    # i 높이 , j: 가로
    for i in range(m):
        for j in range(n):
            if graph[i][j] == 0 and y1 <= i <= y2 and x1 <= j <= x2:
                graph[i][j] = -1

for i in range(m):
    for j in range(n):
        if graph[i][j] == 0 and visited[i][j] == False:
            cnt += 1
            res.append(bfs(i, j))
res.sort()
print(cnt)
for i in res:
    print(i, end=" ")

풀이

문제 자체는 어렵지 않은데 직사각형 입력 받고 그걸 그래프에 표기하는게 좀 오래 걸렸다...🫥