알고리즘
[알고리즘] DFS와 BFS란?
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS(깊이 우선 탐색) DFS는 깊이 우선 탐색으로 그래프를 탐색하는 방법이다. 탐색 순서는 다음과 같다. 그림을 보면 알겠지만 루트 노드에서부터 제일 깊은 곳을 먼저 찍고 옆으로 이동한다. 구현은 스택과 재귀 함수로 구현한다. 장점 목표하는 노드가 깊이 있을 경우 BFS보다 빠르게 찾을 수 있다. 간단하게 구현할 수 있다. 단점 속도가 BFS보다 느리다. 해가 없는 경로에 깊이 빠질 가능성이 있다. 얻어진 해가 최단 경로..
