No Limitation
[BFS] 동일 Set 유형 2 본문
https://www.acmicpc.net/problem/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=' ')
'프로그래밍' 카테고리의 다른 글
[BFS] 트리의 부모 노드 찾기 (0) | 2024.03.28 |
---|---|
[BFS] 일자 기준에 따른 counting (0) | 2024.03.27 |
[BFS] 숨바꼭질 (0) | 2024.03.24 |
[다익스트라] heap을 사용한 다익스트라 예제 연습 (0) | 2024.03.22 |
[SQL] 주의해야 할 유형 (0) | 2024.03.21 |