백준(BOJ) 그래프 순회 - DFS와BFS(1260) Silver2

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

1260번: DFS와 BFS

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

문제해결

그래프 순회 알고리즘의 기본인 DFS와 BFS를 구현하는 문제이며 개념만 알고 있다면 어렵지 않게 해결할 수 있는 문제이다. 다만 주어진 조건에서 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하는 부분을 주의해야 한다.

1. 그래프 구성

• 주어진 조건에 맞게 그래프 구성

  for(ll i=0; i<edges; i++){
        cin >> nodeA >> nodeB;
        graph[nodeA].push_back(nodeB);
        graph[nodeB].push_back(nodeA);
    }
    // 양방향 그래프 구성

2. 각각의 그래프 정렬

• 조건에서 원하는 정점 번호가 작은 것을 방문하기 위하여 각각의 정점들으 오름차순으로 정렬

  for(ll i=1; i<=vertices; i++)
        sort(graph[i].begin(), graph[i].end());

3. DFS 순회 시작

// DFS 탐색 시작
    visit[start_node] = 1;
    stack<ll>s;
    s.push(start_node);
    DFS(graph, visit, s);

 

void DFS(vector<ll>graph[], vector<ll> &visit, stack<ll> &s)
{
    if(!s.empty()){
        ll temp = s.top();
        s.pop();
        cout << temp << " ";
        for(ll i=0; i<graph[temp].size(); i++){
            if(visit[graph[temp][i]] == 0){
                visit[graph[temp][i]] = 1;
                s.push(graph[temp][i]);
                DFS(graph, visit, s);
            }
        }
    }
}

4. visit 벡터 초기화 및 개행문자 추가

• DFS에서 사용했던 visit 벡터 초기화와 정답출력을 위해 개행 문자 추가

for(ll i=1; i<=vertices; i++)
        visit[i] = 0;
    cout << "\n";

5. BFS 순회 시작

// BFS 탐색 시작 
    visit[start_node] = 1;
    queue<ll>q;
    q.push(start_node);
    BFS(graph, visit, q);

void BFS(vector<ll>graph[], vector<ll> &visit, queue<ll> &q)
{
    if(!q.empty()){
        ll temp = q.front();
        q.pop();
        cout << temp << " ";
        for(ll i=0; i<graph[temp].size(); i++){
            if(visit[graph[temp][i]] == 0){
                visit[graph[temp][i]] = 1;
                q.push(graph[temp][i]);
            }
        }
        BFS(graph, visit, q);
    }
}

전체 코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

void DFS(vector<ll>graph[], vector<ll> &visit, stack<ll> &s);
void BFS(vector<ll>graph[], vector<ll> &visit, queue<ll> &q);
void print_graph(vector<ll>graph[], ll vertices)
{
    for(ll i=1; i<=vertices; i++){
        cout << i << "번 Vertex :  ";
        for(ll j=0; j<graph[i].size(); j++){
            cout << graph[i][j] << "-->";
        }
        cout << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    ll vertices = 0;
    ll edges = 0;
    ll start_node = 0;
    ll nodeA, nodeB;

    cin >> vertices >> edges >> start_node;

    vector<ll>graph[vertices+1];
    vector<ll> visit(vertices+1, 0);

    for(ll i=0; i<edges; i++){
        cin >> nodeA >> nodeB;
        graph[nodeA].push_back(nodeB);
        graph[nodeB].push_back(nodeA);
    }
    // 양방향 그래프 구성

    // cout << "================정렬 전====================\n";
    // print_graph(graph, vertices);

    for(ll i=1; i<=vertices; i++)
        sort(graph[i].begin(), graph[i].end());
    // 방문 순서를 지키기 위해 정렬

    // cout << "================정렬 후====================\n";
    // print_graph(graph, vertices);

    // DFS 탐색 시작
    visit[start_node] = 1;
    stack<ll>s;
    s.push(start_node);
    DFS(graph, visit, s);

    for(ll i=1; i<=vertices; i++)
        visit[i] = 0;
    cout << "\n";

    // BFS 탐색 시작 
    visit[start_node] = 1;
    queue<ll>q;
    q.push(start_node);
    BFS(graph, visit, q);
}

void DFS(vector<ll>graph[], vector<ll> &visit, stack<ll> &s)
{
    if(!s.empty()){
        ll temp = s.top();
        s.pop();
        cout << temp << " ";
        for(ll i=0; i<graph[temp].size(); i++){
            if(visit[graph[temp][i]] == 0){
                visit[graph[temp][i]] = 1;
                s.push(graph[temp][i]);
                DFS(graph, visit, s);
            }
        }
    }
}

void BFS(vector<ll>graph[], vector<ll> &visit, queue<ll> &q)
{
    if(!q.empty()){
        ll temp = q.front();
        q.pop();
        cout << temp << " ";
        for(ll i=0; i<graph[temp].size(); i++){
            if(visit[graph[temp][i]] == 0){
                visit[graph[temp][i]] = 1;
                q.push(graph[temp][i]);
            }
        }
        BFS(graph, visit, q);
    }
}