[BOJ] 백준 2606 바이러스 / 너비 우선 탐색(BFS)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

1번 컴퓨터에 바이러스가 감염되면 이와 연결되어 바이러스에 감염되는 컴퓨터의 수를 구하는 문제이다.

1번 컴퓨터(노드)에 연결된 컴퓨터(노드) 개수를 구하면 된다.

 

너비 우선 탐색(BFS) 기법으로 풀이했다.

 

 

💭 풀이 과정

 

 

 

작성 언어: C++

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int visited[101] = {0, };

int bfs(deque<deque<int>> nodes) {
    int virused = 0;
    deque<int> queue;
    // 1번 컴퓨터에서 시작, 방문 처리
    queue.push_back(1);
    visited[1] = 1;
    
    while (!queue.empty()) {
        int now_node = queue.front();
        queue.pop_front();
        
        for (int i = 0; i < nodes[now_node].size(); ++i) {
            int linked_node = nodes[now_node][i];
            // 아직 방문하지 않은 컴퓨터를 찾아서 큐에 넣고
            // 방문처리, 바이러스 감염 수 1 증가
            if (!visited[linked_node]) {
                queue.push_back(linked_node);
                visited[linked_node] = 1;
                virused += 1;
            }
        }
    }
    
    return virused;
}

int main() {
    deque<deque<int>> nodes;
    deque<int> link;
    int total_com = 0, links = 0;
    
    cin >> total_com;
    for (int i = 0; i <= total_com; ++i) {
        nodes.push_back(link);
    }
    
    cin >> links;
    while (links--) {
        int a = 0, b = 0;
        cin >> a >> b;
        // 네트워크는 양방향으로 연결되어 있는 것으로 설정
        nodes[a].push_back(b);
        nodes[b].push_back(a);
    }
    
    for (int i = 0; i <= total_com; ++i) {
        sort(nodes[i].begin(), nodes[i].end()); // 각 노드의 연결정보는 오름차순 정렬
    }
    
    cout << bfs(nodes) << endl;
    
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

구현이 어려운 문제는 아니었는데 방문처리를 큐에 삽입할 때가 아니라 (for 문 내부)

pop_front 할 때 삽입하면 이미 큐에 넣어둔 노드도 다시 삽입하는 문제가 생긴다. => 노드를 중복해서 센다는 것.

 

📌 큐에 삽입하면서 방문처리해서 해결!!