Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[BFS] 동일 Set 유형 2 본문

프로그래밍

[BFS] 동일 Set 유형 2

yesungcho 2024. 3. 27. 16:53

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

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

전형적인 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=' ')