2667 단지번호 붙히기

ylab 2022. 11. 3. 18:00

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

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

#bfs너비우선 탐색
from collections import deque
N = int(input())

#무지성으로 일단 그래프 만들기
graph = []
for _ in range(N):
    graph.append(list(map(int,input())))
#print(N)
#print(graph)
def bfs (graph,x,y):
	#하상좌우
	dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    #큐 만들고
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    cnt =1

    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx>=N or ny< 0 or ny>=N:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
                cnt+=1

    return cnt

count = []

for i in range(N):
    for j in range(N):
        if graph[i][j]==1:
            count.append(bfs(graph,i,j))

count.sort()
print(len(count))

for i in range(len(count)):
    print(count[i])