[백준][알고리즘][C++] 2606 바이러스

문제의 난이도

문제의 난이도 : Silver 2

문제 분석

문제의 난이도는 Silver에서 상위 티어지만,

BFS 알고리즘을 알고 있다면 전혀 어렵지 않다.

이 문제는 상당히 BFS의 정석 같은 문제라고 할 수 있다.

문제를 풀 때 중요한 키는

'컴퓨터 간 연결 관계를 어떻게 표현할 것인가?'

라고 할 수 있다.

문제 해결

컴퓨터 간 연결 관계를 어떻게 표현할 것인가?

다양한 방법이 있을 수 있는데,

1. pair 형태의 벡터로 저장한다.
2. Map에 저장한다.
3. 인접 행렬(0과 1로만 이루어진 행렬)의 형태로 배열에 저장한다.

이런 방법들이 있을 수 있다.

다만, 1번과 2번의 경우 first나 key만 검사하는 것이 아니라 second나 value도 검사해야 한다.

물론 3번도 마찬가지지만 실제로 문제를 풀 때 코드가 더 직관적이다.

그래서 개인적으로는 3번 방법을 이용하여 문제를 풀게 되었다.

(그러나, 메모리 공간에 민감한 문제라면 1번과 2번을 고려했을 것이다.)

해답 코드

#include <iostream>
#include <queue>

using namespace std;

// 인접행렬로 표현한 컴퓨터 간 연결 관계
int computerMap[101][101];

// BFS 알고리즘에서 방문했는지 확인하는 배열
bool visited[101];

// 바이러스에 걸리게 되는 컴퓨터의 수
int cnt;
int N, M;

void bfs() {
    queue<int> q;
    // Starting point는 1번 컴퓨터
    q.push(1);
    
    // -1로 설정한 이유는
    // 1번에서 탐색하면 ++하여 0으로 만들고
    // 그 다음 걸린 것부터 1이 되기 때문.
    cnt = -1;

    while(!q.empty()) {
        int key = q.front();
        q.pop();
        cnt++;

        for(int i=1; i<= N; i++) {
            if(computerMap[key][i] == 1 && visited[i] == false) {
                visited[i] = true;
                q.push(i);
            }
        }
        visited[key] = true;
    }
}

int main() {
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        int x, y;
        cin >> x >> y;
        // 쌍방에 연결관계가 있다는 것을 표현
        computerMap[x][y] = 1;
        computerMap[y][x] = 1;
    }

    bfs();
    cout << cnt;
    return 0;
}