백준[2606] - 바이러스

문제

백준 2606 문제 보기

접근 방법

연결 요소에 대해서 완전탐색으로 문제를 풀수 있다. 연결 돼 있는 요소라면 dfs 탐색을 활용해 방문하고 한번 방문한 곳은 다시 방문하지 않게 chk에 체크를 한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int computer, con;
vector<vector<int>> v(101);
int chk[101];

int dfs(int idx) {
    // 방문 체크
    chk[idx] = 1;
    // 연결되어 있는 모든 요소 방문
    for(int i = 0; i < v[idx].size(); i ++) {
        // 방문하지 않은 곳
        if(chk[v[idx][i]] != 1) {
            dfs(v[idx][i]);
        }
    }
    return 0;
}

int main() {

    cin >> computer >> con;
    for(int i = 0; i < con; i ++) {
        int num, num2;
        cin >> num >> num2;
        // 이차원 배열로 그래프 표시
        v[num].push_back(num2);
        v[num2].push_back(num);
    }

    chk[1] = 1;
    for(int i = 0; i < v[1].size(); i ++) {
        if(chk[v[1][i]] != 1) {
            dfs(v[1][i]);
        }
    }
    int ans = 0;
    for(int i = 0; i < 101; i ++) {
        if(chk[i] == 1)
            ans ++;
    }
    cout << ans - 1;
    return 0;
}