승1's B(log n)

1) DFS(Depth-First Search) 깊이우선탐색 깊이우선탐색은 캐쥬얼하게 말하자면 깊이 들어갈 수 있을 만틈 들어갔다가 더 이상 들어갈 수 없을 때 뒤로 빠져나와 다른 길로 깊이 들어갔다 나왔다 하는 것을 반복하는 방법이라고 할 수 있다. 말로만 들어서는 어려우니 그림을 보면서 이해해보자. 우선 노드의 인덱스가 0부터 7까지 존재하는 그래프를 생각해보자. 각각의 노드들은 서로 다른 노드들과 연결되어 있는데, 이해의 편의를 위해서 가운데처럼 Adjacency List로 만들어보았다. 인덱스가 0인 노드는 인덱스가 1과 2인 노드들과 연결되어 있고, 인덱스가 1인 노드는 인덱스가 0, 3, 4인 노드들과 연결되어 있다. LIFO(Last In First Out)구조인 스택을 이용하면 DFS를 이..