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

 

2667번: 단지번호붙이기

DFS, BFS 둘중 아무거나 사용해도 상관 없을 것 같다.

 

1) 단지 배열 전체 탐색 후 1 발견시 DFS탐색 시작

2) DFS탐색 스택에서 꺼낸 인덱스 값들을 단지 배열에 넣고 조건문 시작

3) 단지 배열이 1이면 0으로 바꿔주고, 카운트, 상하좌우 인덱스 값 배열을 스택에 추가

4) 카운트 값을 result에 저장하고 단지 배열 전체 탐색 끝난 후 정렬

 

전체 코드

import sys

input = sys.stdin.readline

N = int(input())
danji = [[0]*N for _ in range(N)]
stack = []
for i in range(N):
    danji[i] = list(str(input().strip()))
    for j in range(N):
        if danji[i][j] == '1':
            stack.append([i,j])

result = []
def dfs(root):
    stack = [root]
    count = 0

    while stack:
        node = stack.pop()
        i, j = node[0], node[1]
        if danji[i][j] == '1':
            danji[i][j] = '0'
            count += 1
            if i > 0:
                stack.append([i - 1, j])
            if j > 0:
                stack.append([i, j-1])
            if i < N - 1:
                stack.append([i + 1, j])
            if j < N - 1:
                stack.append([i, j + 1])
    result.append(count)

for i in range(N):
    for j in range(N):
        if danji[i][j] == '1':
            dfs([i,j])
result.sort()
print(len(result))
print(*result, sep='\n')