[BOJ][C++] 백준 2606번: 바이러스

문제

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

 

문제 이해

• 컴퓨터가 바이러스에 걸리면, 그 컴퓨터와 네트워크 상에서 서로 연결되어 있는 컴퓨터는 모두 바이러스에 걸린다.
• 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수 출력

 

문제 풀이

🔍 접근

• 네트워크 상에서 연결되어 있는 컴퓨터들을 그래프로 나타낼 수 있다.
• 1번 컴퓨터와 연결된 모든 컴퓨터를 탐색한다.

 

💡 DFS & BFS

• 인접 행렬에 네트워크 상에서 서로 연결되어 있는 컴퓨터의 정보를 저장한다.
• 1번 컴퓨터부터 탐색을 시작해서, 1번 컴퓨터와 연결된 모든 컴퓨터에 방문한다.
• 방문할 때마다 방문 표시를 하고 카운트(바이러스에 걸리는 컴퓨터의 수)를 증가시킨다.

 

코드

1️⃣ DFS

#include <iostream>
#include <vector>

using namespace std;

int n, m, cnt;
vector<vector<bool> > adj;
vector<bool> visited;

void dfs(int com) {
    visited[com] = true;
    cnt++;

    for (int next = 1; next < n + 1; next++) {
        if (adj[com][next] && !visited[next])
            dfs(next);
    }
}

int main() {
    // 입력
    cnt = 0;
    cin >> n >> m;
    adj.assign(n + 1, vector<bool>(n + 1, false));
    visited.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int r, c;
        cin >> r >> c;
        adj[r][c] = true;
        adj[c][r] = true;
    }

    // 연산
    dfs(1);

    // 출력
    cout << cnt - 1;
    
    return 0;
}

 

 

2️⃣ BFS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<vector<bool> > adj;
vector<bool> visited;

int bfs(int com) {
    int cnt = 0;
    queue<int> q;

    q.push(com);
    visited[com] = true;

    while (!q.empty()) {
        com = q.front();
        cnt++;
        q.pop();
        for (int next = 1; next < n + 1; next++) {
            if (!adj[com][next] || visited[next])
                continue;
            visited[next] = true;
            q.push(next);
        }
    }
    return cnt - 1;
}

int main() {
    // 입력
    cin >> n >> m;
    adj.assign(n + 1, vector<bool>(n + 1, false));
    visited.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int r, c;
        cin >> r >> c;
        adj[r][c] = true;
        adj[c][r] = true;
    }

    // 연산 & 출력
    cout << bfs(1);
    
    return 0;
}