[Python] 백준 알고리즘 #2667 단지 번호 붙이기

문제

2667번: 단지번호붙이기

 

풀이

bfs를 활용해서 풀었다. 

import sys
from collections import deque

N = int(input())

field = [[0 for _ in range(N)] for _ in range(N)]

dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

for i in range(N):
    line = sys.stdin.readline()
    for j in range(N):
        field[i][j] = int(line[j])


def bfs(x, y):
    each = 1
    queue = deque()
    queue.append([x, y])
    field[x][y] = 2

    while queue:

        pop = queue.popleft()
        i = pop[0]
        j = pop[1]

        # 인접 1 발견하면 큐에 넣기
        for k in range(4):
            ndr = i + dr[k]
            ndc = j + dc[k]

            if ndr >= 0 and ndr < N and ndc >= 0 and ndc < N and field[ndr][ndc] == 1:
                queue.append([ndr, ndc])
                each += 1
                field[ndr][ndc] = 2

    li.append(each)


count = 0
li = []
for i in range(len(field)):
    for j in range(len(field)):
        if field[i][j] == 1:
            count += 1
            bfs(i, j)

print(count)
for each in sorted(li):
    print(each)