DFS (Depth-First Search)

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용한다.
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
  3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  4. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

---

1. DFS 동작 예시

출처 : 이코테2021

1번기준으로 인접한 노드로 방문을 해야하는데 (2,3,8)이 있다. 이경우 번호가 낮은 (2)를 먼저 방문할 것이다.

 

우선 시작노드가 1이므로 1을 방문처리하고 스택에 1을 삽입한다.

 

여러 개가 인접해있지만 가장 낮은 수부터 방문하기로 했으므로 2에 방문한다.

이에 따라 스택에 방문한 2를 넣는다.

 

 

그다음 낮은 수인 6에 방문한다. 깊이 우선 탐색인데 이처럼 6다음에 연결된 노드가 없으면 

 

스택에서 6을 빼주고 다시 전단계(7)로 올라간다.

 

다시 마찬가지로 그다음 인접한 8로 이동한다.

더이상 방문할 곳이 없으면 계속 거슬러 올라가 노드가 발견될 때까지 올라간다.

---

2. 소스코드

def DFS(graph, v, visited):
    visited[v] = True #현재 노드를 방문 처리(visited 리스트)
    print(v, end=' ') #방문처리된 노드번호
    
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            DFS(graph, i, visited)

• visited리스트를 이용해서 현재 방문한 노드를 방문처리(True)를 한다.
• 방문처리된 노드 번호를 즉각 출력하게 만든다.
• for문을 통해 현재 노드와 연결된 다른 노드를 재귀적으로 방문한다.

 

#0인덱스가 아닌 1번부터 시작하는 경우가 많아 예시를 0번을 비워뒀다. []
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 표현
#모든 노드를 방문하지 않은 False로 표현
visited = [False] * 9

DFS(graph, 1, visited)

• 대부분 코딩테스트에서는 0번 인덱스가 아닌 1번부터 시작하는 경우가 많아 예시를 0으로 비워뒀다. []
• 각 노드가 방문된 정보를 표현하기 위해 visited 리스를 작성했고
• 방문하지 않은 것을 표시하기 위해 False로 초기화했다.

#실행 결과
1 2 7 6 8 3 4 5