2606 - 바이러스

전형적인 그래프 탐색 문제이다. 1번 컴퓨터가 바이러스에 먼저 감염되면, 1번 컴퓨터와 네트워크로 인접한 컴퓨터들이 바이러스에 감염되게 된다. 마찬가지로 x번 컴퓨터가 바이러스에 감염되면, x번 컴퓨터와 인접한 모든 컴퓨터들은 바이러스에 감염된다. 즉 먼저 감염된 1번 컴퓨터를 시작으로 dfs나 bfs를 통해 인접한 컴퓨터들을 탐색하면 되는 문제이다.

🔗 문제 링크

코드

먼저 그래프를 담을 인접 리스트 vector<int> graph[105]와 방문 노드를 저장할 bool visited[105] 를 선언한다. 이 문제에서 단 두 노드간의 연결을 검사할 일이 없고 한 노드와 연결된 모든 노드를 검사하기 때문에 인접 행렬보다 인접 리스트가 더 효율적이다. 그런 다음 main 함수 내부에서 그래프 연결 상태를 입력받아 graph에 담는다. 이 문제에서 가정하는 그래프는 방향성이 없으므로 x와 y 모두에 노드를 삽입해 양방향 간선으로 처리한다. 다음으로 dfs로 구현하기 위해 스택 자료구조를 선언하고 제일 먼저 감염된 1번 노드를 삽입한 뒤 방문 처리를 한다. 이제 스택이 빌 때까지 while 문을 돌며 st.top(); st.pop()을 통해 가장 최근에 방문했던 노드를 꺼내 그 노드와 인접한 미방문 노드들을 모두 탐색하며 스택에 등록하고 방문 처리를 한다. 동시에 cnt++을 통해 감염된 컴퓨터 수를 증가시킨다. while 문을 빠져나오면 탐색이 완료된 것이므로 cnt를 출력하고 프로그램을 종료한다.

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[105];
bool visited[105];
int N, M;

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

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
           
        graph[x].push_back(y);
        graph[y].push_back(x);
    }


    stack<int> st;
    st.push(1);
    visited[1] = true;
    int cnt = 0;
    while (!st.empty()) {
        int node = st.top(); st.pop();
        
        for (int adj : graph[node]) {
            if (visited[adj]) continue;
            cnt++;
            st.push(adj);
            visited[adj] = true;
        }
    }

    cout << cnt << '\n';
    return 0;
}

이 문제는 다음과 같이 재귀 함수와 시스템 스택을 통해 풀 수도 있다.

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[105];
bool visited[105];
int N, M;
int cnt;

void dfs(int node) {
    visited[node] = true;

    for (int adj : graph[node]) {
        if (visited[adj]) continue;
        cnt++;
        dfs(adj);
    }
}


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

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
           
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs(1);

    cout << cnt << '\n';
    return 0;
}

시간복잡도

dfs 탐색에서 최악의 경우 $N$개의 노드를 탐색할 수 있으며( $O(N)$ ), 최대 $2M$개의 간선을 탐색한다( $O(M)$ ). 따라서 시간복잡도는 $O(N+M)$이 된다.