[BOJ알고리즘, C++]#2606_바이러스, 그래프, DFS, BFS

 

#1. 문제

 

---

 

#2. 풀이

 

1. 그래프

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

 

2. DFS

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

 

3. BFS

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

 

5. 시작 노드와 직+간접적으로 연결된 정점 개수를 찾자

1. 시작 정점을 기준으로 DFS와 BFS를 활용하여 정점들을 방문합니다.
2. 정점 방문 시 방문 정점 개수를 증가시켜 줍니다.

 

---

 

#3. 코드

 

1. 스택 DFS 활용

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

int N, M;
int res;

void DFS(int start, unordered_map<int,vector<int>>& graph)
{
    // 방문 여부
    vector<bool> visited(graph.size()+1, false);
    // 스택
    stack<int> s;
    
    s.push(start);
    visited[start] = true;
    // 스택 순회
    while(!s.empty())
    {
        int cur = s.top();
        s.pop();
        
        for(int i=0; i<(int)graph[cur].size(); ++i)
        {
            int next = graph[cur][i];
            if(!visited[next])
            {
                visited[next] = true;
                s.push(next);
                res++;
            }
        }
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // #1. um 컨테이너 형식의 그래프
    unordered_map<int, vector<int>> graph;
    
    // #2. 그래프 구성
    for(int i=0; i<M; ++i)
    {
        int node1, node2;
        
        cin >> node1 >> node2;
        
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
    }
    
    // #3. DFS 호출
    DFS(1, graph);
    
    cout << res;
    
    return 0;
}

 

2. BFS 활용

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

int N, M, res;

void BFS(int start, unordered_map<int, vector<int>>& graph)
{
    // 방문 여부
    vector<bool> visited(graph.size()+1, false);
    // 큐
    queue<int> q;
    
    // 시작 노드 삽입
    visited[start] = true;
    q.push(start);
    
    // queue 순회
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        for(auto& neighbor : graph[cur])
        {
            if(!visited[neighbor])
            {
                visited[neighbor] = true;
                q.push(neighbor);
                res++;
            }
        }
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // #1. um 형식의 그래프 선언
    unordered_map<int, vector<int>> graph;
    // #2. 그래프 구성
    for(int i=0; i<M; ++i)
    {
        int node1, node2;
        
        cin >> node1 >> node2;
        
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
    }
    // BFS 호출
    BFS(1, graph);
    
    // 정답 출력
    cout << res;
    
    return 0;
}

 

---