[백준 알고리즘] 1260번: DFS와 BFS
May 05, 2020
https://www.acmicpc.net/problem/1260
문제
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
풀이
수업시간에 배웠던 내용을 다시 점검하면서 풀어볼 수 있는 문제였다. adjacency list 를 만들어본게 처음이라서 조금 헤맸다. queue 는 반복자나 랜덤 어세스가 불가능해서 처음에 생각했던 vector + queue 로 리스트를 구현하는 것이 아니라 vector + vector 로 구현하는 것이 여러모로 편리한 방법이었다. 이 문제에서 각 엣지는 모두 양방향으로 연결되어 있기 때문에 라스트에 인접노드를 기록하는 과정에서 반대방향으로의 연결 역시 고려해주어야 한다. 그리고 번호가 작은 순서대로 탐색해야하기 때문에, 인접리스트를 만들고 한번 정렬해주어야 한다.
dfs는 visited 마킹 + 재귀적 호출로 쉽게 처리할 수 있었다. 시작점으로부터 인접리스트에 기록된 노드를 하나 방문하고 그 노드를 다시 dfs의 시작점으로 재귀호출해서 계속해서 자식노드를 따라가는 방식이다.
bfs는 구현을 처음해봐서 시간이 조금 걸렸다. 배운대로 큐를 하나 만들고, 시작점을 최초 아이템으로 큐에 넣은 후 visited 마킹을 처리해준다. 그리고 인접리스트에 존재하는 해당 노드의 인접 노드들을 차례대로 방문하면서 visited 마킹과 출력을 해준다. 인접리스트에 있는 노드들은 큐에 들어가서 탐색이 마치면 큐에서 나오게 되기 때문에 큐가 완전히 비어질 때까지 같은 방법으로 탐색을 진행하면 모든 노드를 레벨순서대로 탐색할 수 있다.
코드
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
queue<int> q;
vector<int> visited (1001, 0);
void bfs (vector<vector<int>> adj, int s){
printf("%d ", s);
while(!q.empty()){
int node = q.front();
q.pop();
visited[node] = 1;
for (int i = 0 ; i < adj[node].size() ; i++){
if (visited[adj[node][i]] == 0){
visited[adj[node][i]] = 1;
printf("%d ", adj[node][i]);
q.push(adj[node][i]);
}
}
}
}
void dfs (vector<vector<int>> adj, int s){
visited[s] = 1;
printf("%d ", s);
for (int i = 0 ; i < adj[s].size() ; i++){
if (visited[adj[s][i]] == 0){
visited[adj[s][i]] = 1;
dfs(adj, adj[s][i]);
}
}
}
int main (){
int v, e, s;
scanf("%d %d %d", &v, &e, &s);
vector<vector<int>> adj (v+1);
q.push(s);
for (int i = 0 ; i < e ; i++){
int a, b;
scanf("%d %d", &a, &b);
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 0 ; i <= v ; i++){
sort(adj[i].begin(), adj[i].end());
}
dfs(adj, s);
printf("\n");
for (int i = 0 ; i <= v ; i++){
visited[i] = 0;
}
bfs(adj, s);
}
