https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
www.acmicpc.net
Solution
DFS와 BFS의 기본 문제.
DFS는 말 그대로 깊이 우선 탐색이기 때문에, 시작 정점(V)부터 탐색해서 연결된 정점(e)의 visited가 FALSE이면 그 V 정점과 연결된 정점(e)을 탐색한다. 즉, e와 연결된 또 다른 정점을 찾는다. 이렇게 재귀 형식으로 탐색하는게 DFS.
BFS는 너비 우선 탐색이므로 시작 정점(V)과 연결된 모든 정점을 먼저 탐색하고 큐에 넣는다. 그리고 연결된 정점(e)의 visited에 TRUE 값을 넣어준다. 이렇게 BFS는 큐를 이용하여 탐색한다.
TMI지만 난 방문할 수 있는 정점이 여러 개일 때 정점 번호가 작은 것을 먼저 방문한다는 것을 놓치고 제출했다가 틀렸었다.
'Algorithm > BOJ' 카테고리의 다른 글
| [백준/Python] 14503번 로봇 청소기 (0) | 2020.04.20 |
|---|---|
| [백준/Python] 2178번 미로 탐색 (0) | 2020.04.19 |
| [백준/Python] 1012번 유기농배추 (0) | 2020.04.18 |
| [백준/Python] 14502번 연구소 (0) | 2020.04.15 |
| [백준/Python] 14891번 톱니바퀴 (0) | 2020.04.11 |
,