(매일 BOJ) C++ 1325번 효율적인 해킹

이번 문제는 1325번 효율적인 해킹이다

문제 설명

• N개의 컴퓨터와 M개의 단방향 신뢰 관계가 주어짐
• A B라는 입력은 B 컴퓨터가 A 컴퓨터를 신뢰한다는 뜻
• 한 컴퓨터를 해킹하면, 그 컴퓨터를 신뢰하는 컴퓨터도 해킹 가능
• 가장 많은 컴퓨터를 해킹할 수 있는 시작 컴퓨터 번호를 모두 출력해야 함

문제 접근

단방향 간선이 주어지고, 한 노드에서 시작해 도달 가능한 모든 노드를 세는 문제이므로 DFS 또는 BFS로 해결할 수 있다

1. A B가 주어졌을 때, B → A 방향으로 그래프를 구성해야 함
   • 이유: B를 해킹하면 A도 해킹 가능하기 때문
2. 각 노드를 시작점으로 DFS를 실행해 몇 개의 노드를 해킹할 수 있는지 계산
3. 가장 많이 해킹할 수 있는 노드의 번호를 출력

 

작성코드

#include <bits/stdc++.h>
using namespace std;

int N,M;
int DFS (vector<vector<int>> & v,vector<bool> &, int i);

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    vector<int> cnt_vertex;
    vector<vector<int>> v(N+1);

    for(int i = 0; i < M; i++){
        int a,b;
        cin >> a >> b;
        v[b].push_back(a);
    }

    for(int i = 0; i < N; i++){
        sort(v[i].begin(),v[i].end());
    }

    int max = 0;

    for(int i = 1; i <= N; i++){
        vector<bool> visited (N+1,false);
        int cnt = DFS(v,visited,i);
        if(cnt > max){
            max = cnt;
            cnt_vertex.clear();
            cnt_vertex.push_back(i);
        }
        else if(cnt == max){
            cnt_vertex.push_back(i);
        }
    }

    for(int i : cnt_vertex){
            cout << i << ' ';
    }
}

int DFS (vector<vector<int>> & v, vector<bool> & visited,int i){
    int count_parts = 1;
    visited[i] = true;

    for(int a : v[i]){
        if(!visited[a]){
            count_parts += DFS(v,visited,a);
        }
    }
    return count_parts;
}