[백준] 1260번 DFS와 BFS (C++)

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

문제 설명

그래프의 정점과 간선이 주어진 경우에 대해서 해당 그래프를 DFS로 탐색한 순서, BFS로 탐색한 순서를 출력하는 문제이다.

 

주요 로직

1. DFS 로직 (수도코드 ver)

dfs(int here){
	visited[here] = true;
    for(int there : adj[here]){
    	if(visited[there]) continue;
        dfs(there);
    }
}

2. BFS 로직 (수도 코드 ver)

bfs(int here){
	visited[here] = true;
    q.push(here);
    while(q.size()){
    	int a = q.front();
        q.pop();
        for(auto there : adj[a]){
        	if(visited[there] == false){
            	visited[there] = true;
                q.push(there);
            }
        }
    }
}

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,m,v,a,b;
int visited[1004];
vector<int> adj[1004];
vector<int> dfs_v, bfs_v;

void dfs(int here){
	visited[here] = true;
	dfs_v.push_back(here);
	for(auto it : adj[here]){
		if(visited[it]) continue;
		dfs(it);
	}
	return ;
}

void bfs(int here){
	visited[here] = true;
	queue<int> q;
	q.push(here);
	bfs_v.push_back(here);
	while(q.size()){
		int u = q.front(); 
		q.pop();
		for(auto it : adj[u]){
			if(visited[it]) continue;
			q.push(it);
			visited[it] = true;
			bfs_v.push_back(it);
		}
	}
	return ;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> v;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for(int i=1; i<=n; i++){
		sort(adj[i].begin(), adj[i].end());
	}
	
	fill(&visited[0], &visited[0]+1004, 0);
	dfs(v);
	fill(&visited[0], &visited[0]+1004, 0);
	bfs(v);
	
	for(auto it : dfs_v) cout << it << " ";
	cout << "\n";
	
	for(auto it : bfs_v) cout << it << " ";
	cout << "\n";
	
	return 0;
}