1. Reference

(1)
https://velog.io/@taehyeon96/DFS-BFS-%ED%95%B5%EC%8B%AC-%EC%84%A4%EB%AA%85-%EC%A4%91%EC%9A%94
개인적으로 이 분이 DFS에 관해서 아주 잘 정리해주신 것 같다.

• 참조 대부분의 내용은 이 분의 Velog와 내가 개인적으로 알고리즘 서적 + 내가 풀다가 느낀 점을 바탕으로 정리함.
  (2)
  https://velog.io/@taehyeon96/3.-%EC%9D%B4%EC%BD%94%ED%85%8C-DFS-BFS-%EA%B0%9C%EC%9A%94-%EB%A9%94%EC%9D%B8-%EC%BD%94%EB%93%9C

2. Overview

사실상 알고리즘 테스트에서 나오는 알고리즘들은 이미 기출과 공식적인 뼈대(풀이방법)이 정해져있다. 그리고 해당 알고리즘 풀이법은 암기해야 시간 내에 풀 수 있다. 코테용 언어로 주로 쓰는 자바가 아닌 파이썬을 선택했다.
특히, BFS / DFS는 한국 코딩테스트의 6대 빈출 알고리즘 중 하나!

<<문제를 대할 때 풀이 원칙 3단계>>
아주 직관적으로는 내 머리 속에는 DFS는 나무라고 생각한다. 나무들이 각 가지들이 갈라지는 nodes들이 있듯. 각각의 경우의수(가지들)들로 분리될 수 있는 nodes를 찾는 것이 핵심! 나무가지를 찾고 다니면서 방문기록 찍고 다니면 된다~~ 이게 핵심
그래서 나무 가지를 표현해야하기 때문에 List 2차원 배열일 수밖에 없는겨....ㅎㅎ
1. 어? 문제에서 경우의 수를 찾는다. => 탐색 문제 (BFS 혹은 DFS)임.
그럼 원칙은 DFS로 풀자! 딱 하나 예외 최단거리 경우의 수만 BFS로 풀자.
2. 그럼 도대체 DFS는 한마디로 뭔데? 아래에 있는 공식적인 뼈대대로 풀 거야!
DFS는 재귀함수 = 반복성 = 스택자료구조 -> 결국 반복문과 친구임.
3. 그럼 결국 DFS로 푼다고 하면, 함수 안에 재귀함수를 넣어야하고, 반복적으로 돌려야한다는 이야기네! 반복문의 핵심은 뭐라고? => 시작점과 끝점을 정해주는 것!
4. 아주 정확하게 말하자면, 반복문을 먼저 선언해주고 반복문 안에 재귀함수를 넣어서 재귀함수 다 돌려보는 것!
5. 그럼 공식적인 뼈대대로 시작!

3. Summary

DFS의 공식적인 뼈대 (암기하자)
(1) 일단, 함수에는 파라미터는 3개! 그래프(2차원배열), 방문기록(1차원배열), 인덱스
(2) 반복문 선언 -> 시작점:인덱스 , 끝점:해당 node의 크기(size)
왜 쓴다고? 내가 이 분기점(node)에 연결된 모든 가능성을 다 털어볼라고! 그럴려면 반복적으로 털어야하니깐!

""" Python """

def dfs(graph, v, visited):
    # 3. 방문한 노드(nodes) 체크
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 방문...!
    for i in graph[v]:
    	#4. 현재 노드에서 방문하지 않은 새로운 node를 마주친다면! 재귀호출하세요!!
        if not visited[i]:            # not 연산자<중요>
            dfs(graph, i, visited)

<Parameters 1 - Graph> 
# 1. Input graph : 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],           # 보통 1번부터 있기 때문에 인덱스 0번은 비워둠
    [2,3,8],      # 2번 노드(에 연결된 노드들)
    [1,7],        # 3번 노드
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

<Parameters 2 - Visited : 방문기록>
# 2. 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9         # 리스트 인덱스 0부터 시작이기 때문에 9개

<실행>
dfs(graph, 1, visited)

4. 도대체 DFS란 그래서 무슨 원리야?

여긴 원문의 내용을 바탕으로 정리해주는 게 더 직관적일 거 같아서 원문의 내용을 바탕으로 정리하겠음. 아무리 위의 공식을 외운다고 하더라도 원리를 정확하게 이해해야 이게 왜 저렇게 수렴할 수밖에 없는지를 이해할 수 있음.

To summarize articles in Wikipeida, DFS is an acronym of Depth First Search Algorithm. As, It reaches furthest downsides of nodes, It get backs to the divergent node, which leads to the another way.
That is the point, speaking of nodes, I think It is very useful when you think of it as a tree. Tree has each nodes which diverge branches.
That is why we implements recursive functions. To scrutinize deep downward, It should get back to nodes unless we found all branches linked into a single divergent node.