알고리즘 - DFS(Depth-First Search)

https://youtu.be/7C9RgOcvkvo?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=1585

<DFS 동작예시>

- 무방향 그래프

- 그래프에서는 대부분 번호가 낮은 인접 노드부터 시작한다는 것이 많다.

 

1 -> 2 -> 7 -> (6 or 8)일 때 가장 깊은 6 -> 다른 노드가 없기 때문에 노드 6을 꺼내주면 된다. -> 8 -> 3 -> 4 -> 5

#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)

# 각 노드가 연결된 정보를 표현 2차원 리스트
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
             #1번    2번     3번    4번   5번  6번  7번    8번

# 각 노드가 방문된 정보를 표현 (1차원 리스트) 인덱스 0 사용하지 않기 위해서 +1 해준 값으로!
visited = [False]*9 

dfs(graph,1,visited)

- 이때 그래프에 있는 것은 인접한 노드를 표현한 것입니다.

- [ ] 인덱스 0인 노드는 비워주고 인덱스가 1인 노드부터 시작해줍니다.

 

<노드 1과 인접한 노드들>

 

<노드 2와 인접한 노드들>

 

<노드 3과 인접한 노드들>

- 이런식으로 살펴보았을 떄 직접적으로 간선으로 이어져 있는 노드들만 인접한 노드로 그래프에 2차원 배열로 들어가게 됩니다. 이것을 유의하여 2차원 배열을 넣어주세요.