2606번. 바이러스

문제 링크

바이러스

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> g[101]; // 네트워크 연결 정보를 담은 벡터 배열, 
bool visited[101]; // 방문 여부를 담은 배열
int cnt = 0; // 감염된 컴퓨터의 수

void dfs(int root) { // 깊이 우선 탐색
    cnt++;
    visited[root] = true;
    
    for (int i : g[root]) {
        if (!visited[i]) { // 방문하지 않은 노드에 대해 dfs를 재귀 호출
            dfs(i);  
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[b].push_back(a); // g[b] = {..., a}
        g[a].push_back(b); // g[a] = {..., b}
    }
    dfs(1);
    cout << cnt - 1; // 1번 컴퓨터는 제외하고 출력
    
    return 0;
}

설명

1. 연결된 노드를 벡터 배열에 저장한다.
2. 1번 노드부터 DFS 탐색을 시작한다. 노드를 탐색할 때 마다 cnt를 증가시킨다.
   1. 1번 노드와 연결된 노드를 모두 탐색한다.
   2. 다음 노드부터 연결된 노드를 모두 탐색한다.
3. cnt를 출력한다.

핵심

양방향 그래프이므로 그래프에 삽입할 때 a, b 둘 다 연결시켰다.

네트워크 배열을 어떻게 저장하나 싶었는데 이렇게 저장하는 것이다. 예를 들어 1번 노드와 2, 3번 노드가 연결되어 있고, 2번 노드와 1, 3, 5, 7번 노드가 연결되어 있으면
g[1] = {2, 3}, g[2] = {1, 3, 5, 7} 이렇게 저장된다. (탐색을 하면서 visited = true라면 그 노드는 출력하지 않는다)

배운 점

DFS를 처음 접해봐서 신기했다. 스택 대신 재귀를 사용했다.