[백준] 2606번: 바이러스

짜장범벅·2022년 7월 31일
0

백준

목록 보기
6/26

1 문제

Graph 상의 완전 탐색

2 Idea

DFS를 이용해 완전 탐색
BFS를 이용해도 OK!

3 Code

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

#include <iostream>
#include <vector>

int gDfsAnswer = 0;

void DFS(const std::vector<std::vector<bool>>& graph, std::vector<bool>& visit, const int n, const int current){
    //not visited
    //  -> increase gDfsAnswer
    //  -> do DFS recursively

    ++gDfsAnswer;
    visit[current] = true;

    for (int i=1; i<=n; ++i){
        if ((graph[current][i]) && (!visit[i])){
            DFS(graph, visit, n, i);
        }
    }
}

int CalculateVirusComputer(const std::vector<std::vector<bool>>& graph, const int n){
    int answer = 0;

    //make visit
    std::vector<bool> visit(n+1, false);

    DFS(graph, visit, n, 1);

    answer = gDfsAnswer-1;
        //-1: to ignore starting point 1

    return answer;
}

int main(){
    int n = 0;
    int k = 0;

    std::cin >> n;
    std::cin >> k;

    std::vector<std::vector<bool>> graph(n+1, std::vector<bool>(n+1, false));
        //ignore 0-th

    for (int i=0; i<k; ++i){
        int from = 0;
        int to = 0;

        std::cin >> from >> to;

        graph[from][to] = true;
        graph[to][from] = true;
    }

    std::cout << CalculateVirusComputer(graph, n) << std::endl;

    return 0;
}
profile
큰일날 사람

0개의 댓글