[BOJ] 2667 / 단지번호붙이기 / Python 파이썬

[BOJ] 2667 / 단지번호붙이기 / Python 파이썬

[BOJ] 2667 / 단지번호붙이기 / Python 파이썬

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

2667번: 단지번호붙이기

 

풀이

이중배열로 된 데이터를 탐색하는 문제이다.

 

붙어있는 block 의 개수를 구하기 위하여, deque 로 BFS 를 구현하여 탐색하였다.

 

import sys
from collections import deque
input = sys.stdin.readline


def BFS(r, c):
    dq = deque()
    dq.append((r, c))
    maps[r][c] = 0
    cnt = 1

    while dq:
        y, x = dq.popleft()
        for i in range(4):
            X = x + dx[i]
            Y = y + dy[i]

            if 0 <= Y < N and 0 <= X < N and maps[Y][X]:
                maps[Y][X] = 0
                cnt += 1
                dq.append((Y, X))
    return cnt


N = int(input())
maps = []

for _ in range(N):
    maps.append(list(map(int, list(input().rstrip()))))

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

blocks = []

for r in range(N):
    for c in range(N):
        if maps[r][c]:
            blocks.append(BFS(r, c))

print(len(blocks))
for b in sorted(blocks):
    print(b)