DFS, Depth First Search

DFS는 '깊이 우선 탐색' 으로, 존재하는 자식 노드를 끝까지 탐색한 이후 옆 노드로 들어가서 다시 자식 노드까지 탐색하는 탐색이다.

 

 

 

 

그림과 같은 트리 구조를 DFS 하게 된다면, 

 

[0 -> 1 -> 4 -> 1 -> 5 -> 1 -> 0 -> 2 -> 6 -> 2 -> 0 -> 3 -> 7 -> 3 -> 0] 순서로 이동하게 되고

 

출력값은 [0 -> 1 -> 4 -> 5 -> 2 -> 6 -> 3 -> 7] 순서로 나온다.

 

 

---

[Stack]

 

 

DFS에서는 스택의 자료구조 형태를 사용한다.

 

스택의 형태가 적합한 이유는 스택의 LIFO 라는 특징이 가장 크다고 생각한다.

 

탐색과정을 스택에 저장해두다가, 다음 경로 탐색이 불필요하다고 생각하면 / 최근 경로로 되돌아가야 하기 때문이다.

 

다음 경로 탐색이 불필요하다고 판단하게 만들려면, 찾고자 하는 특정 값으로만 향하게 하기 위해 여러 조건문이 필요하다.

 

---

[BackTracking]

 

 

여러 조건을 통해 '해당 경로의 탐색은 불필요하다' 라고 판단된다면, 스택에 저장된 경로 정보를 이용해 되돌아간다.

 

이 과정을 백트래킹 (BackTracking)이라고 하며, 불필요한 연산을 줄일 수 있으며 원하는 값만을 얻기에 필수적이다.

 

---

 

1주차 문제에서 특히 기억나는 DFS 문제 두개이다.

 

[10971 외판원 순회 2]

 

 

탐색을 하는 함수 안에는, 탐색을 완료했을 때 종료를 위한 조건문이 필수적이다.

 

계속해서 함수 자신을 호출하므로, 값만 챙기고 나가야 한다.

 

line 7의 len(visited)는 탐색의 횟수를 표현하기 위한 문장인데, 다음에는 depth로 짧고 간결하게 표현할 수 있게 노력해야겠다.

 

line 13에 있는 많은 조건문들이 백트래킹을 하기 위한 조건들이다. 해당 조건들을 통과했다는 건, 다음 경로의 탐색이 유의미하다는 것

 

line 14에서 visited라는 배열에 next를 넣어준다. 방문 경로를 저장하는 것으로, line 16에서 pop() 사용으로 스택과 같이 최근 값을 뺀다.

 

pop()으로 바로 next 인자를 빼는 이유는, 해당 인자 정보를 포함한 하나의 새로운 함수가 호출되었기 때문이다.

 

 

---

[2309 일곱 난쟁이]

 

이 코드는 위에 있는 코드와 굉장이 유사하게 보인다. (풀때는 몰랐다)

 

함수에 입력해야 하는 요소에 필수적으로 '탐색할 깊이'가 들어가는 것이다. '현재 경로의 위치'도 들어가야한다.

 

위 코드와 같은 종료를 위한 조건문, 백트래킹을 하기 위한 조건문, 유의미한 경로라고 판단될 경우 현재 위치를 넣고 함수 호출,  pop()

 

문제를 풀때는 dfs라는 '알고리즘 문제에 자주 나오는 유형' 문제구나 라는 생각만 했는데, 팀원들에게 설명을 하려다 보니

 

DFS 문제의 코드는 유사한 형태를 취하고 있는 걸 알게 되었다. 

 

알고리즘 문제 풀이 경험이 많은 사람들이 문제를 보자마자 카테고리화 시킨 이후 공통적인 풀이법을 빠르게 가져갈 수 있는 이유를 알게 됨.