[Python] 단지번호붙이기 - 백준 (DFS)

해당 글은 백준 2667번 문제 '단지번호붙이기'를 다룬다.

 

문제

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

2667번: 단지번호붙이기

 

설명

DFS로 방문하지 않았으면 index를 증가시켜 상하좌우를 방문한다. 그리고 단지내 집수를 구하기 위해 house_count 리스트를 만들어서 dfs를 돌때마다 증가시킨다. 마지막에 정렬한 후 출력하면 된다.

 

코드

def dfs(x, y, index):
    data[x][y] = index
    house_count[index-2] += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < n:
            if data[nx][ny] == 1:
                dfs(nx, ny, index)

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

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

house_count = []
index = 2
for i in range(n):
    for j in range(n):
        if data[i][j] == 1:
            house_count.append(0)
            dfs(i, j, index)
            index += 1

house_count.sort()
count = len(house_count)
print(count)
for i in range(count):
    print(house_count[i])