[BOJ] 2606번 바이러스 (C++)

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

2606번: 바이러스

 

DFS를 이용한 문제 풀이

#include <iostream>
using namespace std;

int map[101][101];
int visit[101];
int com, cnt;

void num_of_virus_com(int node) {
    visit[node] = 1;

    for (int i = 1; i <= com; i++) {
        if (!visit[i] && map[node][i] == 1) {
            cnt++;
            num_of_virus_com(i);
        }
    }
}

int main() {
    int n, u, v;
    cin >> com >> n;

    for (int i = 0; i < n; i++) {
        cin >> u >> v;
        map[u][v] = map[v][u] = 1;
    }

    num_of_virus_com(1);
    cout << cnt << endl;

    return 0;
}

방향이 없는 그래프 문제는 쌍방을 연결하는 2차원 map이 필요하다. 방문한 위치 정보를 저장하는 1차원 visit 배열도 선언해준다.

이 두 배열은 함수에서 반복적으로 사용하여야 하기 때문에 파라미터로 넘기는 대신 전역변수로 선언했다.

com과 cnt는 각각 컴퓨터의 개수, 감염된 컴퓨터의 수를 의미한다. 이 또한 전역변수로 선언했다.

 

DFS는 재귀 함수 형태와 Stack 구조로 구현이 가능한데 위 코드는 재귀 함수 형태로 구현한 것이다.

 

visit[node] = 1;          현재 node를 방문 표시

for(int i = 1; i <= n; i++)         1번부터 모든 컴퓨터에 대하여 2가지 조건 비교

i번째 컴퓨터를 방문하였는지 (visit[i]이 0인지 -> !visit[i])

&&

현재 node와 i번째 컴퓨터가 연결되어 있는지 (map[i][node] == 1)

이 두 조건을 만족한다면, i번째 컴퓨터를 방문한 것으로 바꾸고 바이러스에 감염된 컴퓨터 개수를 증가시킨다.   cnt++;

마지막으로 i번째 컴퓨터와 연결된 새로운 컴퓨터를 찾는 재귀함수를 실행한다.    num_of_virus_com(i);

 

BFS를 이용한 문제 풀이

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

int map[101][101];
int visit[101];
int com, cnt;

void num_of_virus_com2(int start) {
    visit[start] = 1;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int i = 1; i <= com; i++) {
            if (!visit[i] && map[node][i] == 1) {
                q.push(i);
                visit[i] = 1;
                cnt++;
            }
        }
    }
}

int main() {
    int n, u, v;
    cin >> com >> n;

    for (int i = 0; i < n; i++) {
        cin >> u >> v;
        map[u][v] = map[v][u] = 1;
    }

    num_of_virus_com2(1);
    cout << cnt << endl;

    return 0;
}

BFS에서는 queue를 사용한다.

DFS와 다른 점은 파라미터가 node가 아닌 start이다. 함수의 호출이 main함수에서의 한 번 뿐이기 때문에, 시작 지점에 대한 정보만 필요하기 때문이다.

 

현 위치를 방문 표시하고     visit[start];

queue에 start 위치를 push 시키고, queue에 값이 들어있기 때문에 while(!q.empty())는 queue가 빌 때까지 루프를 돌게 된다.

루프에 들어온 이후 queue의 맨 앞 데이터를 확인하여 저장하고     int node = q.front();

확인이 완료된 데이터를 빼낸다.     q.pop();