[백준 2606] 바이러스

🔗알고리즘 문제

DFS를 이용하여 쉽게 풀 수 있던 문제이다. 이제 그래프 탐색에 조금 익숙해진 것 같아서 뿌듯하다 : )

문제 분석

이 문제는 간단히 말해 그래프의 정보가 주어질 때 1번 노드와 연결되있는 노드의 수를 구하는 문제이다.

발상 & 알고리즘 설계

1번 노드에서 부터 시작하여 연결 된 노드를 모두 탐색해야하므로 DFS를 사용해서 해결해야겠다고 생각하였다.

1번노드에서 부터 탐색을 시작한 후 연결된 노드를 발견할 때 마다 answer를 하나씩 증가시켜주었다. 탐색이 끝난 후 answer를 출력해주었다.

코드

#include<iostream>
#include<vector>

using namespace std;

int answer = 0;

void dfs(vector<int> *graph, int v, bool *visited){
    visited[v] = true;

    for(int i = 0; i < graph[v].size(); i++){
        int next = graph[v][i];

        if(visited[next] == false){
            ++answer;
            dfs(graph, next, visited);
        }
    }
}

int main(){
    vector<int> graph[101] = {};
    bool visited[101] = {};

    int n;
    int m;

    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int cur;
        int next;

        cin >> cur >> next;

        graph[cur].push_back(next);
        graph[next].push_back(cur);
    }

    dfs(graph, 1, visited);

    cout << answer;
}