[백준] 2606.cpp : 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

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

// dfs 함수
void dfs(vector<vector<int>>& v, vector<bool>& checked, int idx)
{
    // 체크되었는지 검사
    if(checked[idx]) return;
    checked[idx] = true;
    // 재귀호출
    for(int i = 0 ; i < v[idx].size() ; i++)
    {
        dfs(v, checked, v[idx][i]);
    }
}

int main(void)
{
    int n, line;
    int answer = 0;
    cin >> n;
    cin >> line;

    // 컴퓨터 연결 정보
    vector<vector<int>> v(n);
    // 체크 정보
    vector<bool> checked(n, false);

    int lf, rf;
    // 노드들 양방향 연결
    for(int i = 0 ; i < line ; i++)
    {
        cin >> lf >> rf;
        v[lf - 1].push_back(rf - 1);
        v[rf - 1].push_back(lf - 1);
    }
    // 1번 컴퓨터에 연결된 친구들만 확인
    dfs(v, checked, 0);
    
    // 1번 컴퓨터는 제외니까 빼준다
    for(int i = 1 ; i < n ; i++)
    {
        if(checked[i]) answer++;
    }
    cout << answer << '\n';
}

 

[Approach]

1.  어제 골드단계 dfs 문제를 풀어서 그런지 굉장히 쉬워 보인다. 연결된 컴퓨터들 수만 세어주면 될 듯.

 

[Point]

1. 컴퓨터들의 번호가 0 이 아닌 1번부터 시작하는 것을 주의하자.

2. 연결할때는 양방향으로 해줄 것!

3. 굳이 사이즈 지키려고 레퍼런스 거는 것보다 그냥 전역 변수로 놓는게 훨씬 편해 보이긴 한다.

 

[More]

1. 반복문 안에서 쓰이는 변수들을 for 문 선언시 같이 해주는 것도 깔끔해 보인다.

2. 난해하지만 한줄로 표현되는 함수 (4610339)