[백준] 2667번: 단지번호붙이기

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

2667번: 단지번호붙이기

이전에 풀었던 문제보다 쉽게 구현이 가능한 문제이다.

bfs탐색을 연습하기 위해 bfs로 구현하였다. dfs로 구현하여도 클리어는 가능한 문제로 보인다.

또한 이번에는 단순 list,pop(0)을 이용하지 않고 deque를 선언하여 구현하였다.

 

from collections import deque

n = int(input())

arr = []
for i in range(n):
    arr.append(list(map(int,input())))

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

q = deque()
total = 1
pri = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            total += 1
            q.append((i,j))
            arr[i][j] = total
            cnt = 1
            while q:
                x, y = q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] == 1:
                        arr[nx][ny] = total
                        cnt += 1
                        q.append((nx,ny))


            pri.append(cnt)

pri.sort()
print(total-1)
for i in range(len(pri)):
    print(pri[i])