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

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

2583번: 영역 구하기

 

풀이 :

1. 그래프 탐색 문제라고 생각하여 BFS 풀이법을 사용하기로 생각.

2. 기존 알고리즘 문제의 경우와 달리 y축이 뒤바뀌어 있기때문에 이부분을 원래 풀던 방식으로 변경하고자 (M-y2, M-y1)으로 코드 작성

3. 직사각형이 그려진 부분을 1 값으로 저장 -> graph[j][k] = 1

4. bfs 구현 -> 상 하 좌 우로 이동하면서 빈 영역의 개수를 count

 

코드 : 

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

M,N,K = map(int,input().split())

graph = []
for i in range(M):
    graph.append([0] * N)

visited = [[False] * N for _ in range(M)]
answer = []

for i in range(K):
    x1,y1,x2,y2 = map(int,input().split())
    for j in range(M-y2,M-y1):
        for k in range(x1,x2):
            graph[j][k] = 1

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

def bfs(t1,t2):
    count = 0
    q = deque()
    q.append([t1,t2])
    visited[t1][t2] = True
    while q:
        y,x = q.popleft()
        count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and graph[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append([ny,nx])
    if count != 0:
        answer.append(count)
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0 and not visited[i][j]:
            bfs(i,j)
answer.sort()      

print(len(answer))
print(" ".join(map(str,answer)))