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

풀이

DFS, BFS 두 방법으로 풀 수 있는 문제였습니다. 저는 DFS 로 풀어보았습니다.

 

아래 코드에서 특정 x,y 좌표에서 dfs 함수를 한번 거치면, graph 상의 해당 x,y 좌표를 포함하여 상하좌우로 인접한 모든 1 을 0 으로 바꿉니다. 즉, dfs 함수를 한 번 거칠 때마다 아파트 단지수인 apart_complex 변수를 1 더해줍니다. 또, 그 과정에서 0으로 바꿀 때마다 단지내 집의 수를 구해주기 위해서 apart_unit 변수에 1 을 더해주는 작업을 합니다. 끝까지 탐색을 해주면, graph 의 모든 원소는 0으로 바뀌어 있을 겁니다. 1 이면 방문 해야하며, 0 이면 방문 완료 혹은 방문 하지 않아도 됨 입니다.

 

import sys
 
input = sys.stdin.readline
 
n = int(input())
graph = [[] for _ in range(n)]
dx = [0, 0, -1, 1]  # 상하좌우
dy = [-1, 1, 0, 0]
apart_complex = 0
apart_unit = 0
apart_unit_list = []
 
for i in range(n):
    graph[i].extend(list(map(int, list(input().rstrip()))))
 
 
def dfs(x, y):
    graph[x][y] = 0
    global apart_unit
    apart_unit += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < n and 0 <= ny < n) and graph[nx][ny] == 1:
            dfs(nx, ny)
 
 
for i in range(n):
    for j in range(n):
        if graph[j][i] == 1:
            dfs(j, i)
            apart_complex += 1
            apart_unit_list.append(apart_unit)
            apart_unit = 0
 
print(apart_complex)
for i in sorted(apart_unit_list):
    print(i)