백준 영역 구하기 bfs

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

2583번: 영역 구하기

 

 

• 마지막으로 전체 for문 돌릴 때 graph[i][j] == 0이면 1로 업데이트 해줘야 함
• 이 부분 안 하면 칸이 두 개 이상일 때 첫 칸 재방문하게 됨
• *sorted(result) 하면 result 배열을 오름차순 정렬하고 한 줄에 내용 출력

 

from collections import deque
m,n,k = map(int, input().split())
result = []
graph = [[0] * n for _ 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

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

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

    return cnt

for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
        	#여기서 방문 업데이트 안 하면 칸이 두 개 이상일 때 
            #첫 방문칸 다시 탐색함
            graph[i][j] = 1
            result.append(bfs(i,j))

print(len(result))
print(*sorted(result))