[Algorithm] 백준 2667 단지번호붙이기 | 파이썬 DFS

※ 2667 단지번호붙이기

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

문제 해결 TIP

이코테의 음료수 얼려 먹기 문제의 응용 버전이라고 생각하면 된다. DFS를 이용하여 연결된 모든 노드들을 방문하고 count를 해준다. 집이 있는 곳이라면, 문제에 나와 있는 것처럼 단지번호를 붙여준다. (집의 유무인 1과 헷갈리지 않기 위해 단지번호는 2부터 붙여주었다.) 집을 모두 방문한 후 그래프의 최종 상태는 마지막 주석을 확인하기 바란다.

 

전체 코드

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int,input())))
#graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1], [1, 1, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 0, 0, 0]]

def dfs(x,y):
    if x<=-1 or x>=N or y<=-1 or y>=N:
        return False
    if graph[x][y] == 1:
        graph[x][y] = result+2 #단지번호 붙이기
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False
#단지 수 출력
result = 0
for i in range(N):
    for j in range(N):
        if dfs(i,j) == True:
            result += 1
print(result)
#단지에 속한 집의 개수 저장
house = []
for i in range(result):
    count = 0
    for row in graph:
        count += row.count(i+2)
    house.append(count)
#오름차순 정렬
house = sorted(house)
for i in house:
    print(i)
#graph = [[0, 2, 2, 0, 3, 0, 0], [0, 2, 2, 0, 3, 0, 3], [2, 2, 2, 0, 3, 0, 3], [0, 0, 0, 0, 3, 3, 3], [0, 4, 0, 0, 0, 0, 0], [0, 4, 4, 4, 4, 4, 0], [0, 4, 4, 4, 0, 0, 0]]