DFS의 개념

DFS는 Depth-First Search의 약자로, 깊이 우선 탐색이라고도 부릅니다. 그래프나 트리에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

위의 숫자가 DFS의 탐색 순서입니다. DFS의 동작방법은 두가지로 이뤄집니다.

• 일단 내려갈 수 있을 만큼 내려가기
• 내려갈 수 없다면 돌아오기

DFS의 구현 방법

DFS의 구현 방법은 2가지 입니다.

1. 스택
2. 재귀
   둘 중 재귀를 많이 사용합니다. 그러나 재귀 역시 스택과 같은 원리이기 때문에 스택이라고 볼 수 있습니다.

DFS 구현 코드

adj는 가로 13, 세로 13의 크기를 가진 2원 배열입니다.

adj = [[0] * 13 for i in range(13)]

# adj 출력하기
for j in range(13):
  print(adj[j])

위의 노드와 선으로 구성된 그림처럼 0->1, 1->2, 1->3...에 1을 설정합니다.

adj[0][1] = adj[0][4] = adj[1][2] = adj[1][3] = adj[4][5] = 1

dfs 함수를 구현합니다.

def dfs(n):
  print(n)
  for i in range(13):
    if adj[n][i] == 1:
      dfs(i)

전체코드:

adj = [[0] * 13 for i in range(13)]
adj[0][1] = adj[0][4] = adj[1][2] = adj[1][3] = adj[4][5] = 1

def dfs(n):
  print(n)
  for i in range(13):
    if adj[n][i] == 1:
      dfs(i)

dfs(0)

출력 화면