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

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

2667번: 단지번호붙이기

 

간만에 BFS문제

 

뭔가 익숙해지면 BFS가 젤 쉬운거같다. 실버라 그런가

 

다른 BFS와 비슷하게 돌면서 방문처리를 진행하면서 큐에 넣고 출력해주면서 cnt, sum을 계산에 정답 리스트에 넣은 다음 출력해주면 정답 완성이다.

from collections import deque
n = int(input())

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

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

dq = deque()

answer = []
cnt = 0

for i in range(n):
    for j in range(n):
        s = 1
        if arr[i][j] == 1:
            cnt+=1
            dq.append((i , j))
            arr[i][j] = 0

            while dq:
                x, y = dq.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] = 0
                        s+=1
                        dq.append((nx, ny))
            answer.append(s)


print(cnt)
answer.sort()

for i in answer:
    print(i)

 

완성