깊이 우선 탐색(DFS)

DFS(깊이 우선 탐색)

1. DFS(Depth First Search)란?

깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 방법이다.

그래프는 노드(Node)와 간선(Edge)로 표현되며 노드는 정점(Vertex)라고도 한다.

그래프는 인접리스트(리스트로 그래프의 연결관계 표현)와 인접행렬(2차원 배열로 그래프의 연결 관계를 표현)로 표현할 수 있다.

DFS(깊이우선탐색)는 스택 자료구조를 사용하며 동작과정은 아래와 같다.

1.  탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2.  스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.  
    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3.  2번위 과정을 더 이상 수행할 수 없을 때까지 반복한다.

2. 예시 코드

def dfs(graph, v, visited):
    visited[v] = True                   # 현재 노드 방문 처리
    print(v, end=' ')
    for i in graph[v]:                  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 (graph[v]에 v와 연결된 노드들의 정보가 들어있음)
        if not visited[i]:              # 만약 i가 방문이 True가 아니라면 (방문하지 않았다면)
            dfs(graph, i, visited)      # dfs로 graph[v]의 i 노드 dfs처리 (계속 깊어짐)

n = int(input())                          # 노드의 개수
graph = [[] * (n + 1)]

for _ in range(1, n+1):
  array = list(map(int, input().split()))
  graph.append(array)

visited = [False] * (n + 1)             #[0]은 사용 x

dfs(graph, 1, visited)                  # 1부터 깊이우선탐색 시작

3. 예시 입출력

  같은 행은 해당행의 index와 연결된것이다.(노드1은 노드2,노드3,노드8과 연결)

  입력 : 
  (노드1)  2 3 8
  (노드2)  1 7
  (노드3)  1 4 5
  (노드4)  3 5
  (노드5)  3 4
  (노드6)  7
  (노드7)  2 6 8
  (노드8)  1 7

  출력 :
  노드 1에서 dfs를 구하면
  output = 1 2 7 6 8 3 4 5