[BFS] 동일 Set 유형 2

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

2583번: 영역 구하기

 

전형적인 BFS 유형.
하지만 문제 상 "모눈 종이"의 눈금이라는 것이 x와 y축의 개념이 혼동이 될 수 있는 예제로 주의해야할 거 같다.

코테는 어떤 알고리즘이냐 파악도 중요하지만 못지 않게 국어 능력이 중요하다... 문제의 조건을 잘 파악해야 한다.

from collections import deque
M, N, K = [int(x) for x in input().split()]

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

for _ in range(K) :
    ### 꼭지점 x,y 여기 주의....!
    start_y, start_x, end_y, end_x = [int(x) for x in input().split()]
    for i in range(start_y,end_y) :
        for j in range(start_x,end_x) :
            ### 여기 항상 주의하자, indexing이 거꾸로 된다는 거..!
            visited[j][i] = 1

CLUSTER = 2
queue = deque()

move_x = [-1,1,0,0]
move_y = [0,0,-1,1]

def BFS(queue,cnt) :
    while queue :
        x, y = queue.popleft()
        for i in range(4) :
            after_x = x+move_x[i]
            after_y = y+move_y[i]

            if after_x < 0 or after_y < 0 or after_x >= M or after_y >= N :
                continue

            if visited[after_x][after_y] == 0 :
                visited[after_x][after_y] = CLUSTER
                queue.append([after_x,after_y])
                cnt += 1
    return cnt

cnt_dic = {}

for i in range(M) :
    for j in range(N) :
        if visited[i][j] == 0:
            cnt = 1
            queue.append([i,j])
            visited[i][j] = CLUSTER
            cnt = BFS(queue,cnt)
            cnt_dic[CLUSTER] = cnt
            CLUSTER += 1
            
print(CLUSTER-2)
for final_cnt in sorted(cnt_dic.values()) :
    print(final_cnt, end=' ')