BOJ - 1260. DFS와 BFS (C++)

1260. 노드와 간선으로 이루어진 DFS, BFS

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

1260번: DFS와 BFS

 

[풀이]

노드와 간선으로 BFS, DFS 문제를 해결해야 하는 경우, 아래 그림의 이론을 바탕으로 코드를 짜야한다.

간선을 vector<int> adj[1000] 으로 노드를 int vis[1000] 로 구현한다.

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1002];
int vis1[1002];
int vis2[1002];
int N,M,V;

void dfs(int cur){
	cout << cur << ' ';
	vis1[cur] = 1;
	for(int i:adj[cur]) if (vis1[i] == 0) dfs(i);
	return;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> V; 
	for(int i=0; i<M; i++) {
		int u,v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=N; i++) sort(adj[i].begin(), adj[i].end());
		
	// DFS
	dfs(V);	
	cout << '\n';

	// BFS
	queue<int> Q;
	Q.push(V); vis2[V] = 1;
	while(Q.size()){
		int cur = Q.front();
		cout << cur << ' '; Q.pop();
		for(int i:adj[cur]){
			if (vis2[i] == 0) {
				Q.push(i);
				vis2[i] = 1;
			}
		}
	}
}