문제링크
https://www.acmicpc.net/problem/1260
조건
- 시간 제한 : 2s
- 메모리 제한 : 128MB
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
해설
DFS와 BFS를 다루는 문제이다. 이 문제를 풀면서 DFS 와 BFS를 처음 접해서, 개념정리를 해두었다. 해당 글의 본문을 복사하여 이 글의 해설과 풀이로 사용하겠다.
DFS
Depth First Search(깊이 우선 탐색) 방법은 특정 노드에서 시작하여 갈 수 있는 곳까지 깊숙히 들어가면서 탐색을 진행한다. 도달할 수 있는 node가 없다면(제일 깊은 node를 방문한 뒤에는) 다른 node로 이동할 수 있을 때 까지 뒤로 거슬러 올라온 뒤 다시 다른 경로로 깊숙하게 들어가면서 탐색을 반복한다.DFS는 들어갈 수 있는 가장 깊은 곳까지 들어갔다가, 다음으로 진출할 수 있는 정점을 찾아 한 칸씩 뒤로 간다는 점에서 stack구조를 활용하여 구현이 가능하다.
DFS 구현 방법
DFS 함수를 실행하여 하나의 노드를 방문하고 나서, 해당 노드에서 나아갈 수 있는 노드들을 하위 노드로 생각하고 하위 노드들에 대해 DFS 함수를 실행하면서 재귀적으로 함수를 실행시킨다. 하위 노드들에 대해서도 똑같이 나아갈 수 있는 노드들로 하위 하위 노드들을 분할하여 재귀적으로 DFS 함수를 실행시킨다.
한 노드로 나아갔음을 나타내기 위해서 스택에 현재 방문한 노드를 push 해준다. 특정한 노드를 방문하고 있을 때, 스택에는 해당 노드를 방문하기 위한 경로가 담겨있다.
하나의 하위 노드 set을 모두 방문하고 나서 더이상 갈 곳이 없는 경우, 다른 방문할 수 있는 노드가 나올 때 까지 스택에서 node를 pop하면서 뒤로 후퇴한다. 방문할 수 있는 노드가 있다면 (하위 노드 set에 대해 재귀적으로 함수 실행) 해당 노드를 스택에 push 하면서 탐색을 이어나간다.
DFS 코드로 구현
// 노드는 1~N까지 있다.
// map에는 from node -> to node 로 가는 edge가 있다면 map[from][to]에 1이 담겨있다.
int map[N][N] = {0, };
bool visited[N] = {false, };
stack<int> S;
void DFS(int s) {
// visited 배열에 s번째 노드를 방문했음을 기록하고
// 스택에 s를 담아준다.
visited[s] = true;
S.push(s);
// s 아래에 있는 하위 노드들에 대해 처리
// s번째 노드에서 방문할 수 있는 노드들에 대해 아직 방문한 적이 없다면 DFS 함수를 재귀실행해준다.
for(int i = 1; i <= N; i++) {
if(map[s][i] && !visited[i]) DFS(i);
}
// s를 스택에서 빼고 s보다 앞에 있는 (선행하는) 노드의 DFS 함수에 함수 흐름을 념겨준다.
S.pop();
return;
}
BFS
Breadth First Search(너비 우선 탐색)은 특정 노드에서 시작하여 인접한 노드들을 먼저 방문하면서 탐색을 하는 방법을 말한다. 쉽게 말해, 시작점에서 가까운 점을 먼저 방문하고, 멀리있는 점들을 나중에 방문한다. BFS는 가까운 노드부터 우선하여 탐색하기 때문에, 모든 경로를 탐색하는 DFS와 다르게 좀 더 빠르게 경로를 찾을 수 있다. 시작 점에서 가까운 순서대로 차례대로 노드를 처리하기 때문에, Queue 자료구조를 이용하면 쉽게 구현이 가능하다.
BFS 구현 방법
시작 노드에서 가까운 순서대로 큐에 노드를 담는다. 처리하는 순서는 아래 그림과 같다. 시작 노드로부터 같은 거리에 있는 노드들끼리 차례로 처리를 하여 점점 멀리있는 노드까지 탐색해나간다.
현재 5번 노드를 탐색하고 있다고 가정하자. 큐의 front에는 5번 노드가 있다. 5번 노드를 pop하고, 5번 노드에서 방문할 수 있는 8, 9번 노드를 큐에 push 한다. 이후 6, 7번 노드를 방문하고 나서 8, 9번 노드를 방문하게 될 것이다. 이러한 방식으로 찾고자 하는 노드가 나올 때 까지 경로를 탐색할 수 있다. 간선끼리의 가중치가 동일하다면, 시작 노드에서 특정한 노드까지의 비용(거리)을 구할 수 있다.
BFS 코드 구현
// 노드는 1~N까지 있다.
// map에는 from node -> to node 로 가는 edge가 있다면 map[from][to]에 1이 담겨있다.
int map[N][N] = {0, };
bool visited[N] = {false, };
void BFS(int s) {
// BFS 처리를 위한 Queue를 하나 선언해주고, 시작 노드를 담아준다.
queue<int> BFSQ;
BFSQ.push(s);
// 큐가 빌 때 까지 아래 코드를 반복한다.
while(!BFSQ.empty()) {
// current에 큐의 front에 있는 노드를 가져오고 pop시킨다.
int current = BFSQ.front();
BFSQ.pop();
// 만약 current 노드를 방문하지 않았다면 방문하였다고 처리를 해준다.
// 방문한 노드가 이미 queue에 담겨있을 수도 있으므로, 처리해주어야 한다.
if(!visited[current]) {
cout << current << ' ';
visited[current] = true;
}
// current 노드가 방문할 수 있는 하위 노드들을 큐에 push한다.
for(int i = 1; i <= N; i++) {
if(map[current][i] && !visited[i]) {
BFSQ.push(i);
}
}
}
}
풀이
이 문제에서는 가장 처음 끝까지 도달한 노드에 대한 경로를 출력하는 것이 목표이므로, 함수를 실행하면서 방문하는 노드를 출력하고, 모든 경로를 탐색한 경우 함수를 종료하면 된다.
DFS에 대해서는 함수가 하나의 노드를 방문할 때 재귀적으로 호출되므로, 함수가 한 번 호출될 때 마다 현재 노드를 출력해준다.
void DFS(int s) {
cout << s << ' ';
visited[s] = true;
for(int i = 1; i <= N; i++) {
if(map[s][i] && !visited[i]) DFS(i);
if(i == N) return;
}
}
BFS에 대해서는 Queue에 방문하는 노드가 순서대로 들어오는데, Queue에 중복하여 들어오는 노드가 있기 때문에, BFS 함수를 실행해주면서 노드들을 이미 방문했는지를 검사해준다. 만약 아직 방문하지 않은 노드라면 출력을 해주면 된다.
void BFS(int s) {
queue<int> BFSQ;
BFSQ.push(s);
while(!BFSQ.empty()) {
int current = BFSQ.front();
BFSQ.pop();
if(!visited[current]) {
cout << current << ' ';
visited[current] = true;
}
for(int i = 1; i <= N; i++) {
if(map[current][i] && !visited[i]) {
BFSQ.push(i);
}
}
}
}
메인 함수에서 필요한 값들을 입력받고 DFS, BFS 함수를 실행해주면 원하는 결과를 얻을 수 있다.
int main() {
cin >> N >> M >> V;
for(int i = 0; i < M; i++) {
int from, to;
cin >> from >> to;
map[from][to] = 1;
map[to][from] = 1;
}
DFS(V);
cout << '\n';
init();
BFS(V);
cout << '\n';
}
코멘트
BFS, DFS… 분명 쉬워보이는데 왜이리 혼자 구현하는게 어렵지…? 군대 다녀오면서 확실히 머리가 굳었나보다. ㅜㅜㅜㅜ
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int map[1001][1001] = {0, };
bool visited[1001] = {false, };
int N, M, V;
void init() {
for(int i = 0; i <= 1000; i++) {
visited[i] = false;
}
}
void DFS(int s) {
cout << s << ' ';
visited[s] = true;
for(int i = 1; i <= N; i++) {
if(map[s][i] && !visited[i]) DFS(i);
if(i == N) return;
}
}
void BFS(int s) {
queue<int> BFSQ;
BFSQ.push(s);
while(!BFSQ.empty()) {
int current = BFSQ.front();
BFSQ.pop();
if(!visited[current]) {
cout << current << ' ';
visited[current] = true;
}
for(int i = 1; i <= N; i++) {
if(map[current][i] && !visited[i]) {
BFSQ.push(i);
}
}
}
}
int main() {
cin >> N >> M >> V;
for(int i = 0; i < M; i++) {
int from, to;
cin >> from >> to;
map[from][to] = 1;
map[to][from] = 1;
}
DFS(V);
cout << '\n';
init();
BFS(V);
cout << '\n';
}
/*
https://sihyungyou.github.io/baekjoon-1260/ 쵝오!! ㅜㅜㅜ
*/
Uploaded by Notion2Tistory v1.1.0