코딩테스트-백준

DFS BFS 문제 (1206)

젼뀨 2024. 12. 14. 23:31

DFS는 깊이 우선 탐색으로, 스택이나 재귀를 사용해 한 방향으로 끝까지 탐색 후 되돌아 가는 탐색 방식이다.
모든 경로를 탐색할 때나 백트래킹에서 자주 사용한다.
 
BFS는 너비 우선 탐색으로, 큐를 사용해 가까운 노드부터 차례대로 탐색한다.
최단거리 문제나 단계적 탐색에 많이 사용한다.

DFS와 BFS 1260

더보기

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

문제풀이
 
정점(노드)의 개수 n,
간선(엣지)의 개수 m,
탐색 시작할 정점의 번호를 v로 입력 받는다.
 
dfs를 위한 방문배열과 bfs를 위한 방문배열로 각 각 초기화 해준다.
 
벡터에 그래프를 저장해준다.
양방향 처리를 위해 아래와 같이 서로 연결해주었다.

graph[n1].push_back(n2);
graph[n2].push_back(n1);

 
dfs와 bfs는 서로 다른 자료구조를 쓴다는 것 외에는 같은 방식으로 구현해 주었다.
 
[dfs] 
1. 스택에 시작점 v를 삽입한다. 
2. 스택에서 노드를 pop한 뒤 방문 배열을 true로 전환해준다.
3. pop한 노드의 (방문한 적 없는) 인접 노드를 다시 스택에 삽입해준다.
3-1. 노드가 작은 것 부터 방문하기 위해 벡터를 정렬해준다.
4. 스택이 빌 때 까지 반복해준다.
 
[bfs]
1. 큐에 시작점 v를 삽입한다.
2. 큐에서 노드를 pop한 뒤 방문 배열을 true로 전환해준다.
3. pop한 노드의 (방문한 적 없는) 인접 노드를 다시 스택에 삽입해준다.
3-1. 노드가 작은 것 부터 방문하기 위해 벡터를 정렬해준다.
4. 큐가 빌 때 까지 반복해준다.
 
이를 코드로 구현하면 이렇다.

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector <int> graph[10001];
bool dfsVisited[10001] = {};
bool bfsVisited[10001] = {};

void dfs(int start) {
	stack<int> st;
	st.push(start);
	while (!st.empty()) { //스택 비면 끝
		int node = st.top();
		st.pop();

		if (!dfsVisited[node]) {
			dfsVisited[node] = true;
			cout << node << " ";

			//작은 노드 우선 방문을 위해 내림차순으로 정렬해줌
			sort(graph[node].rbegin(), graph[node].rend());
			//인접 노드들 스택에 추가
			for (int next : graph[node]) {
				st.push(next);
			}
		}
	}
}

void bfs(int start) {
	queue<int> q;
	q.push(start);
	while (!q.empty()) { //큐 비면 끝
		int node = q.front();
		q.pop();

		if (!bfsVisited[node]) {
			bfsVisited[node] = true;
			cout << node << " ";

			sort(graph[node].begin(), graph[node].end());
			//인접 노드들 큐에 추가
			for (int next : graph[node]) {
				q.push(next);
			}
		}
	}
}

int main() {
	int n, m, v;
	cin >> n >> m >> v;

	for (int i = 0; i < m; i++) {
		int n1, n2;
		cin >> n1 >> n2;
		//양방향 연결
		graph[n1].push_back(n2);
		graph[n2].push_back(n1);
	}

	dfs(v);
	cout << "\n";
	bfs(v);
	
	return 0;
}