70. C++ 백준 2606 번 바이러스 자세한 설명

안녕하세요 코딩하는 덕구입니다.

C++ 백준 2606 번 바이러스 입니다.

그래프탐색 문제입니다.

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

2606번: 바이러스

 

 

 

랜선에 연결된 컴퓨터가 감염이 되므로

DFS, BFS 를 통한 그래프 탐색으로 풀 수 있습니다.

시작 지점부터 그래프를 탐색하면서 방문하느 노드당 1개씩 카운트 해주면

연결된 컴퓨터들을 한번씩 방문하면서 카운트를 하게 되겠죠.

 

위의 직관으로 코드를 구현해봅시다. 

저번과는 다르게 이번에는 리스트 형식으로 그래프를 표현해보겠습니다.

 

먼저 그래프를 표현할 행렬 graph와, 방문한지 안한지 체크하기 위한 행렬 visited 를 선언합니다.

int graph[MAX][MAX] = {0,};
int visited[MAX] = {0,};

 

M개의 간선(랜선)이 있으므로 M 번 반복하며 간선 x, y를 입력받아 그래프에 1로 표시 합니다.

for(int i = 1; i <= M; i++){
    cin >> x >> y;
    graph[x][y] = 1;
    graph[y][x] = 1;
}

 

그리고 그래프 탐색을 위한 BFS를 구현해 줍니다,

방문 예정 노드가 없을 때 까지  반복하며 queue에서 노드를 불러옵니다.

while (!qu.empty())

노드를 불러오고 나서 방문한 노드를 세는 변수인 cnt를 1 늘려줍니다.

 

이후 V와 연결된 노드를 탐색하며 아직 방문하지 않은 노드를 찾게되면

방문하며 queue에 삽입합니다.

for(int j = 1; j <= N; j++) {
    if (graph[i][j] == 1 && visited[j] == 0) {
        qu.push(j);
        visited[j] = 1;
    }
}

 

그리고 방문했던 노드들의 개수를 return 해 줍니다.

return cnt;

이 값을 출력해주면 되겠죠.

 

C++백준 2606 번 바이러스 최종 코드 입니다.

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 101
using namespace std;
int graph[MAX][MAX] = {0,};
int visited[MAX] = {0,};
int N, M, cnt = 0;

int BFS(int V){
    queue<int> qu;
    int i;
    qu.push(V);
    visited[V] = 1;
    while (!qu.empty()){
        i = qu.front();
        qu.pop();
        cnt++;
        for(int j = 1; j <= N; j++) {
            if (graph[i][j] == 1 && visited[j] == 0) {
                qu.push(j);
                visited[j] = 1;
            }
        }
    }
    return cnt;
}
int main(){
    int x, y;
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> x >> y;
        graph[x][y] = 1;
        graph[y][x] = 1;
    }
    cout << BFS(1) - 1;

    return 0;
}

 

C++백준 2606 번 바이러스 이었습니다. 감사합니다.