[BOJ] 1260 : DFS와 BFS

Drakk·2021년 7월 15일

알고리즘 문제풀이

목록 보기

6/22

💉문제 내용

💉입출력

🧺입력
첫째 줄에 정점의 개수 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

🔮예제 출력1
1 2 4 3
1 2 3 4

🔮예제 입력2
5 5 3
5 4
5 2
1 2
3 4
3 1

🔮예제 출력2
3 1 2 5 4
3 1 4 2 5

🔮예제 입력3
1000 1 1000
999 1000

🔮예제 출력3
1000 999
1000 999
💉문제 분석

🔋분류

BFS, DFS

🔋난이도

실버II

💉문제 풀이

🔋해법

이 문제는 단순하게 dfs와 bfs를 순서대로 실행해주면됩니다.
주의할점은 인접노드부터 먼저 가야합니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 1001;
int adj[MAX][MAX];

std::vector<int> dfs(int start, int N){
	std::vector<int>ans;
	
	std::stack<int>s;
	std::vector<bool> visit(N + 1, false);
	s.push(start);
	visit[start] = true;
	ans.push_back(start);
	
	while(!s.empty()){
		int x = s.top();
		s.pop();
		
		for(int i=1;i<=N;++i){
			if(!visit[i] && adj[x][i]){
				visit[i] = true;
				s.push(x);
				s.push(i);
				ans.push_back(i);
				break;
			}
		}
	}
	
	return ans;
}

std::vector<int> bfs(int start, int N){
	std::vector<int>ans;
	
	std::queue<int>q;
	std::vector<bool> visit(N + 1, false);
	q.push(start);
	visit[start] = true;
	ans.push_back(start);
	
	while(!q.empty()){
		int x = q.front();
		q.pop();
		
		for(int i=1;i<=N;++i){
			if(!visit[i] && adj[x][i]){
				visit[i] = true;
				q.push(i);
				ans.push_back(i);
			}
		}
	}
	
	return ans;
}

int main() {
	int M, N, S;
	std::cin >> N >> M >> S;
	for(int i=0;i<M;++i){
		int a, b;
		std::cin >> a >> b;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}
	
	for(auto const& a : dfs(S, N)) std::cout << a << " ";
	std::cout << '\n';
	for(auto a : bfs(S, N)) std::cout << a << " ";
}