[BOJ] 2606 : 바이러스

Drakk·2021년 7월 12일

2606 BFS C boj 바이러스 알고리즘

알고리즘 문제풀이

목록 보기

3/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

🧺출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

🔋예제 입출력

🔮예제 입력1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
🔮예제 출력1
4

💉문제 분석

🔋분류

BFS, DFS

🔋난이도

실버III

💉문제 풀이

🔋해법

우선 시작지점이 1이라고했으니까,
for문은 0부터시작이아니라 1부터시작해야하구요.
연결되었으면서 방문하지않은 모든지점을 순회만 하면됩니다.
이 부분은 bfs를 써서 풀었습니다.
이거는 재귀함수쓰는방법도있고, 큐쓰는방법이있는데,
저는 개인적으로 재귀함수가 익숙하지가 않아서,
큐를 사용하는 방법을 썼습니다.

🔋소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX (101)

//모든 지점을 저장하기 위한 컨테이너
std::vector<int> adj[MAX];

void bfs(int N, int start){
    int ans = 0;
    std::queue<int>q;
    q.push(start); //시작지점 큐에 저장
    std::vector<bool>visit(N + 1, false);
    visit[start] = true; //시작지점 방문함.

    while(!q.empty()){
    	//cur : 현재지점
        int cur = q.front();
        q.pop();

	//현재지점과 연결된 모든지점을 순회
        for(int i = 0;i<adj[cur].size();++i){
            //next : 다음으로 갈 지점
            int next = adj[cur][i];
            
            //만약 이미 방문한 지점이라면 안갈거임..!
            if(visit[next]) continue;
            
            //방문처리
            visit[next] = true;
            q.push(next);
            
            //이것이 답을 연산하는 부분!
            ++ans;
        }
    }

    std::cout << ans;
}

int main(){
    int N, M;
    std::cin >> N >> M;
    for(int i=1;i<=M;++i){
        int a, b;
        std::cin >> a >> b;
        
        //반드시 서로를 가리켜줘야합니다!
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bfs(N, 1);
}