[백준] 2583번

백준 2583번

BFS

💗내 풀이💗

직사각형 넓이를 넓이가 1이 되게 잘라주고 애초에 0으로 다 초기화 하되 색칠이 된 사각형은 1로둔다. 그 단계를 하는것이

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]=1

이 코드이다.

그 다음에 값이 0인 사각형은 분리된 영역이라는 뜻이니깐 1로 칠해주고(그래야지 안 겹침) bfs함수를 돌게 한다. 그 값(cnt)을 res라는 리스트에 추가해준다.

bfs함수를 살펴보면 위아래양옆으로도 0이면 그 0으로 가면 되니깐 그렇게 돌게 for문을 만들어주고 0이라면 다시 queue에 추가를 해주고 cnt값을 올려준다,

💗내 코드💗

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

def bfs(i,j):
    queue=deque()
    queue.append((i,j))
    d=[(-1,0),(1,0),(0,-1),(0,1)]
    cnt=1
    while queue:
        y,x=queue.popleft()
        for dy,dx in d:
            Y,X= y+dy,x+dx
            if (0<=Y<M)and (0<=X<N)and graph[Y][X] ==0:
                graph[Y][X]=1
                queue.append((Y,X))
                cnt+=1
    return cnt
          
M,N,K=map(int,input().split())
graph = [[0]*N for i in range(M)]

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]=1
            
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j]==0:
            graph[i][j]=1
            res.append(bfs(i,j))
print(len(res))
print(*sorted(res))