[C++][BFS / DFS] 백준 2606번 문제 풀이

 

 

 

간단한
BFS or DFS 문제

◎ Data structure는 Deque를 사용함

◎ adj_list 먼저 만들고 DFS Search로 답을 구함 (BFS 사용해도 됨)

◎ adj_list , check를 전역 변수로 선언 하지 않고 매개변수로 보내줌 ( 동적 할당을 위해 )

 

 

 

Code

 

// BaekJoon 2606
// Title : Virus
// URL : https://www.acmicpc.net/problem/2606

#include <iostream>
#include <deque>

using namespace std;

void DFS(deque<int> adj_list[] ,deque<bool> &check , int i , int &cnt){
    check[i-1] = true;

    for(int j = 0 ; j < adj_list[i-1].size() ; ++j){
        if(check[adj_list[i-1][j] - 1] == false){ DFS(adj_list,check , adj_list[i-1][j], cnt) ; cnt++; }
    }
}

int main(int argc , char** argv){

    int cmpr , num , first , second;
    int cnt = 0;

    cin >> cmpr >> num;

    deque<int> adj_list[cmpr];
    deque<bool> check(cmpr , false);
    
    // Making adj_list
    
    while(num--){
        
        cin >> first >> second;

        adj_list[first - 1].push_back(second);
        adj_list[second - 1].push_back(first);

    }
    
    // DFS search
    
    DFS(adj_list , check , 1 , cnt);
    
    cout << cnt;
}

 

 

 

https://www.acmicpc.net/problem/2606

2606번: 바이러스