인생자취

1. 들어가기 그래프에 표시된 모든 노드를 탐색하는 방법으로는 시작점을 기준으로 일정한 방향으로 탐색하는 것이 효율적이다. 이때, 효율적인 탐색 방법으로는 깊이 우선 탐색(DFS;Depth First Search)과 너비 우선 탐색(BFS;Breadth First Search)이 대표적이다. 필자는 이번 글에서 깊이 우선 탐색 알고리즘을 중심으로 다뤄볼 것이다. 2. 깊이 우선 탐색 그래프 정점(꼭짓점)이 1, 2, 3, 4, ... , N 개가 있다고 하자. 깊이 우선 탐색은 시작점을 1 이라고 할 때, 1 에서 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 2에 방문하고, 꼭짓점 2에 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 3를 반복한다. 이때 인접한 모든 꼭짓점을 방문한 경우, 이전에 마지막으로..