[Baekjoon] 1260번: DFS와 BFS

🥅 문제

https://www.acmicpc.net/problem/1260

 

🔍 설계

DFS와 BFS를 구현하는 과정에서 올바르게 출력하면 되는 문제이다.

 

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 조건이 있으므로, 연결한 정점을 정렬해야 한다. 간선의 수가 최대 10000개이므로, 양방향을 고려하면 총 간선의 수는 20000개이다. 정렬을 하면, O(NlgN)이므로 시간 제한을 초과하지 않는다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;	
int n, m, v, a, b;
vector<vector<int>> adj_list(1001);
vector<bool> visited(1001);

void dfs(int cur_point){
	visited[cur_point] = true;
	cout << cur_point << " ";
	for (int i=0; i<adj_list[cur_point].size(); i++){
		int new_point = adj_list[cur_point][i];
		if (!visited[new_point]){
			dfs(new_point);
		}
	}	
}

void bfs(int start_point){
	queue<int> q;
	q.push(start_point);
	visited[start_point] = true;
	cout << start_point << " ";
	while (!q.empty()){
		int cur_point = q.front();
		q.pop();
		for (int i=0; i<adj_list[cur_point].size(); i++){
			int new_point = adj_list[cur_point][i];
			if (!visited[new_point]){
				visited[new_point] = true;
				q.push(new_point);
				cout << new_point << " ";
			}
		}
	}
}


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> v;
	for (int i=0; i<m; i++){
		cin >> a >> b;
		adj_list[a].push_back(b);
		adj_list[b].push_back(a);
	}
	for (int i=1; i<=n; i++){
		sort(adj_list[i].begin(), adj_list[i].end());
	}
	dfs(v);
	visited = vector<bool>(1001);
	cout << "\n";
	bfs(v);
	return 0;
}

 

📝 메모

BFS를 구현하는 과정에서 정점 번호가 작은 것을 먼저 방문하기 위해 우선순위 큐를 사용하려 했으나 방문 순서가 맞지 않게 되는 문제가 발생한다.