Graph (DFS,BFS)(basic) - 1260 C++

문제

---

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 
정점 번호는 1번부터 N번까지이다.
https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 
 
 

개요

---

문제를 보면 제일 먼저 그래프 문제인 척하는 트리문제라는 생각이 든다.
단지, 자식노드와 부모노드의 관계가 아닌 정점과 정점사이의 관계라는 것 외에는 다른 점이 없다.
만약 본인이 아직 DFS와 BFS에 대해 잘 모르고 구현해 본 적이 없다면 관련 개념을
한 번 확인 해보면 쉽게 풀 수 있을 것이다.

 
 
 

개념

---

 

그래프는 '정점'과 '간선' 두가지로 이루어져 있다.
그래프 내부에 있는 각 노드들을 '정점(vertex)'이라고 부르고, 그 정점과 정점 사이를 이어주는 것을 '간선(edge)'이라고 부른다.
그래프에는 여러 가지 종류가 있다. 하지만 크게 두 가지로 볼 수 있는데,
첫 번째는 directed graph : 방향을 가지는 그래프
두 번째는 undirected graph : 방향을 가지지 않는 그래프
이번 문제에서는 간선이 양방향이므로 undirected graph를 사용하게 될 것이다.

Undirected Graph

 
 
 

과정

---

그래프의 구현 방식은 인접행렬, 인접리스트 두 가지가 있다.
두 개의 정확한 차이점은 다른 글에서 다루도록 하고 이번 문제에서는 인접 리스트를 이용해 풀 것이다.
(직접 전부 구현하기에는 난이도 있는 문제가 아니어서 STL을 이용해 간단하게 풀었다.)
 
vector<int> 자료형의 배열을 만들어 각 정점마다 간선으로 연결되어 있는 다른 정점을 push 해주는 것만으로도 
그래프를 작성할 수 있고 그다음에 dfs와 bfs함수를 작성하고 실행만 해주면 간단하게 풀린다.
이때 주의할 점은 간선이 양방향이므로 한쪽 방향으로만 push 하는 것이 아닌 반대방향도 해주어야 한다.

 
 
 

코드

---

#include<iostream>
#include<vector>
#include<queue> //bfs를 위한 Q
#include<algorithm>
using namespace std;

vector<int> graph[1001]; //** 자료형이 vector<int> 인 배열을 생성 (index 1001개)
bool visited[1001] = {false, };

void dfs(int cur){
    if(visited[cur]==true){
        return;
    }
    visited[cur]=true;
    cout << cur <<' ';
    for(int next : graph[cur]){ //현재 vertex와 연결되어 있는 다른 vertex 탐색 후 dfs 실행
        dfs(next);
    }
}

void bfs(int root){ //bfs
    queue<int> q;
    q.push(root);
    visited[root] =true;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << ' ';
        for(int next : graph[cur]){
            if(visited[next]==false){
                q.push(next);
                visited[next]=true;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int ver, edg, root;
    cin >> ver >> edg >> root;

    int a, b;
    for(int i = 1; i<=edg; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1; i<=ver; i++){
        sort(graph[i].begin(),graph[i].end());
    }

    dfs(root);
    for(int i = 1; i<=ver; i++){  //dfs 실행 후에 visited 다시 초기화
        visited[i] = false;
    }
    cout<<'\n';
    bfs(root);

}