1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
DFS와 BFS의 구현을 묻는 아주 간단한 문제이다.
우선, DFS와 BFS의 의미는 다음과 같다.
DFS : Depth-First Search (깊이 우선 탐색) / BFS : Breadth-First Search (너비 우선 탐색)
DFS는 함수의 재귀 호출을 이용하여 소스코드로 구현하게 되지만, BFS의 경우엔 자료구조 Queue를 사용하여 소스코드로 구현하는것이 일반적이다. 필자는 C++ STL의 Queue 자료구조를 사용하여 구현하였다.
DFS와 BFS의 소스코드는 다음과 같다.
다음 두 탐색 알고리즘을 활용하여 백준 #1260를 풀었다.
728x90
'Algorithm > BOJ' 카테고리의 다른 글
| [백준] #1918 후위 표기식 (0) | 2021.08.22 |
|---|---|
| [백준] #17609 회문 (0) | 2021.08.19 |
| [백준] #1254 팰린드롬 만들기 (0) | 2021.08.17 |
| [백준] #4948 베르트랑 공준 (0) | 2021.08.15 |
| [백준] #7576 토마토 (0) | 2021.08.09 |