[백준 알고리즘] 2583번 영역 구하기, 파이썬(python)

2583, 영역 구하기

📁 문제 출처

 

💡 생각

• 예시에 있는 그래프를 위로 뒤집으면 좌측 상단이 (0, 0)인 그래프가 된다
• 그렇다면 입력을 받을 때 x1, y1, x2, y2 이렇게 받고 그래프에 그려줄 때는 2중 for문으로 (y1, y2) (x1, x2) 이렇게 받으면 예시와 같은 그래프를 그려줄 수 있다.

 

🛠 나의 코드

from  collections import deque
import sys
input = sys.stdin.readline
 
m, n, k  = map(int, input().split())
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0 , 0]
 
def bfs(graph, a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 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 nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = 1
                queue.append((nx, ny))
                cnt += 1
    return cnt
 
graph = [[0] * n for i in range(m)]
 
for i 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] = 1
 
result = []
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            result.append(bfs(graph, i, j))
 
print(len(result))
result.sort()
for i in result:
    print(i, end=' ')

 

✔️ 배운 점 및 주의할 점

• 예시를 직접 펜으로 그려보고 이것저것 많은 시도를 해보면 아이디어를 얻을 수 있다.