[백준(python)] 2583 영역 구하기

📌 난이도, 유형

난이도 : 실버1
유형 : 그래프 이론, 그래프 탐색, DFS, BFS
시간제한 : 1초
메모리제한 : 128MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

import sys
from collections import deque

input = sys.stdin.readline

M, N, K = map(int, input().split())
graph = [[0] * M for _ in range(N)]

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

for _ in range(K):
    a, b, c, d = map(int, input().split())
    for i in range(min(a, c), max(a, c)):
        for j in range(min(b, d), max(b, d)):
            graph[i][j] = 1


def bfs(i, j):
    queue.append((i, j))
    graph[i][j] = 1
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= M or graph[nx][ny] == 1:
                continue
            if graph[nx][ny] == 0:
                queue.append((nx, ny))
                graph[nx][ny] = 1
                cnt += 1
    return cnt


num = 0  # 영역의 개수
result = []
queue = deque()
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            num += 1
            result.append(bfs(i, j))
result.sort()
print(num)
for i in result:
    print(i, end=" ")

---

📝 해설

이 문제에서 중요한건 좌표값을 어떻게 표현할 것인가? 인것 같다.

어차피 영역의 넓이 구하는건 BFS나 DFS 사용하면 간단히 풀린다.

문제에서는 좌측하단을 (0,0)으로 줬는데

출력부분을 보면 각 영역의 넓이를 오름차순으로 출력하라고 했으니 그래프의 방향은 상관없다.

나는 좌측상단을 (0,0) 기준으로 문제를 풀었다.

for _ in range(K):
    a, b, c, d = map(int, input().split())
    for i in range(min(a, c), max(a, c)):
        for j in range(min(b, d), max(b, d)):
            graph[i][j] = 1

좌표 4개를 입력받고
x는 x축끼리(a,c) y는 y축끼리(b,d) 계산을 한다.
저걸로 그래프를 채워주면

0 1 0 0 0 0 0
1 1 1 1 0 0 0
1 1 1 1 0 0 0
0 1 0 0 1 1 0
0 0 0 0 1 1 0

이런식으로 만들 수 있다.

이제 BFS나 DFS를 사용해서 0인 영역의 넓이를 구하면 끝