[BOJ알고리즘, C++]#1260_DFS와 BFS, DFS, BFS

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 그래프

[자료구조]#6_그래프

 

2. DFS

• [정의] : 깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다.
• [특징] : 깊이 우선 탐색은 한 노드에서 시작해 그래프의 깊은 부분을 우선적으로 탐색하는 방법입니다.
• [동작 방식] : DFS는 일반적으로 재귀적으로 호출하는 방법과 스택을 활용하는 방법이 있습니다.
  1. 재귀적 호출
  2. 스택

 

3. BFS

• [정의] : BFS(너비 우선 탐색)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다.
• [특징] : BFS는 현재 상태에서 가장 인접한 정점들을 우선적으로 탐색하는 방법입니다.
• [동작 방식] : BFS는 큐를 활용하여 구현 가능합니다.
  1. 큐

 

4. 오름차순 정렬, DFS는 역순, BFS는 정순

1. 입력 받은 간선 정보를 2차원 벡터에 저장하고, 각 벡터를 오름차순 정렬해줍니다.
2. 스택을 활용한 DFS의 경우, 현재 정점의 인접 정점을 역순으로 순회하며 스택에 삽입합니다.
3. 큐를 활용한 BFS의 경우, 현재 정점의 인접 정점을 차례대로 순회하며 큐에 삽입합니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, V; 

void DFS(int start, unordered_map<int, vector<int>>& graph)
{
    vector<bool> visited(N+1, false);
    stack<int> s;
    
    s.push(start);
    
    while(!s.empty())
    {
        int cur = s.top();
        s.pop();
        
        if(!visited[cur])
        {
            visited[cur] = true;
            cout << cur << ' ';
        }
        
        for(int i=(int)graph[cur].size()-1; i>= 0; --i)
        {
            if(!visited[graph[cur][i]])
            {
                s.push(graph[cur][i]);
            }
        }
    }
}

void BFS(int start, unordered_map<int, vector<int>>& graph)
{
    vector<bool> visited(N+1, false);
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        cout << cur << ' ';
        
        for(int i=0; i<(int)graph[cur].size(); ++i)
        {
            if(!visited[graph[cur][i]])
            {
                visited[graph[cur][i]] = true;
                q.push(graph[cur][i]);
            }
        }
    }
    
}


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

    cin >> N >> M >> V;
    
    unordered_map<int, vector<int>> graph;
    
    while(M--)
    {
        int a, b;
        cin >> a >> b;
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 인접 정점 목록을 오름차순 정렬
    for(auto& pair : graph)
    {
        sort(begin(pair.second), end(pair.second));    
    }
    
    // #1. DFS
    DFS(V, graph);
    
    cout << '\n';
    
    // #2. BFS
    BFS(V, graph);
    
    return 0;
}

 

---