그래프 - DFS 구현 (2)

개요

https://4sii.tistory.com/517

그래프 - DFS 구현

위 내용과 이어진다.

 

이전에는 알파벳으로 된 노드들로 DFS하는 방법을 알아봤는데

이번엔 숫자로 이루어진 DFS 알고리즘을 알아볼 것이다. 

특히, 각 노드들에 대해 작은 순서부터 진행한다는 큰 특징이 있는데

 

코딩테스트에서 DFS를 번호가 낮은 순서부터 처리하도록 명시하는 경우가 종종 있기 때문에

해당 방법에 대해 알고 있는 것은 중요하다고 볼 수 있다.

 

코드

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * len(graph)

dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5