백준 2606 - 바이러스(C++)

문제 링크입니다 https://www.acmicpc.net/problem/2606

2606번: 바이러스

간단한 bfs,dfs 문제였습니다. 저는 bfs로 풀었습니다.

 

문제 조건

출력 예시

 

문제 접근 방법

1. 연결된 컴퓨터들을 입력받은뒤, 각각의 백터에 저장한다.

2. BFS를 1번 컴퓨터 시작한다.

 

 

문제 접근 방법 - 1번

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

연결된 컴퓨터들을 입력받은뒤, 각각의 백터에 저장했습니다. 이렇게 저장한다면, 한 컴퓨터에서 어떤 컴퓨터들이 연결되었는지 확인할 수 있습니다. BFS는 물론, DFS로 구현할 때도, 이 부분은 필요합니다.

 

 

문제 접근 방법 - 2번

void bfs(int start) {
    int cnt_virus = 0;
    check[start] = 1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = 0; i < com[x].size(); i++) {
            if (check[com[x][i]] == 0) {
                cnt_virus++;
                check[com[x][i]] = 1;
                q.push(com[x][i]);
            }
        }
    }
    cout << cnt_virus;
}

check[] 배열은 각 점을 방문했는지의 여부를 알려주는 배열입니다. 1번 컴퓨터부터 시작하니, 1번부터 시작합니다.

queue에 1를 넣어주면서 시작합니다. 1번에 연결된 컴퓨터들을 전부 확인해줍니다. com 백터에는 각 번호에서 연결된 컴퓨터들의 정보들이 저장되어 있으니 하나하나 확인해줍니다. 

만약 갈 수 있는 컴퓨터들 중에서 전에 방문했던 지점이 있으면 다시 방문할 필요는 없으니 건너뜁니다. 아니라면 그 지점을 큐에 넣어줌으로써 그 지점을 확인해줍니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int num, line;
vector<int> com[101];
int check[101];

void bfs(int start) {
    int cnt_virus = 0;
    check[start] = 1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = 0; i < com[x].size(); i++) {
            if (check[com[x][i]] == 0) {
                cnt_virus++;
                check[com[x][i]] = 1;
                q.push(com[x][i]);
            }
        }
    }
    cout << cnt_virus;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> num >> line;
    for (int i = 0; i < line; i++) {
        int x, y;
        cin >> x >> y;
        com[x].push_back(y);
        com[y].push_back(x);
    }
    bfs(1);
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!