132 효율적인 해킹 c++ (dfs/bfs)

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

 

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

예제 입력 1 

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2

 

 

 

푼후기

 

이문제는 어떠한 컴퓨터를 해킹했을때 이 해킹이 얼마나 연쇄적으로 많은 컴퓨터에 영향을 미칠 수 있는지 파악하며, 가장 큰 영향을 미치는 컴퓨터(정점)을 찾는 문제이다. 각컴퓨터를 시작점으로하여 dfs/bfs로 수행하여서 해킹했을때의 컴퓨터의 총수를 구한다. 이후에 한번에 가장많이 해킹할 수 있는 컴퓨터의 번호들을 오름차순으로 출력하는 문제이다.

 

즉 dfs/bfs에 대한 이해가 있어야하며 그래프에대한 이해가있어야 접근할 수 있는 문제이다.그럼 풀이를 보도록 하겠다.

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,mx,visited[10001],dp[10001];
vector<int> v[10001];


int dfs(int here){
    visited[here] = 1;
    int ret = 1;
    for(int there : v[here]){
        if(visited[there]) continue;
        ret += dfs(there);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        v[b].push_back(a);
    }

    for(int i =1; i<=n; i++){
        memset(visited,0,sizeof(visited));
        dp[i] = dfs(i);
        mx = max(dp[i],mx);
    }
    for(int i=1; i<=n; i++) if(dp[i] == mx) cout << i << " ";



    return 0;
}

 

dfs 메소드

1. dfs 메소드로 해킹할 수있는 컴퓨터의 총 수를 재귀적으로 계산했다.

2. 이미 방문한 컴퓨터(노드는) 다시 방문하지않도록 visited로 해줬다.

3. 그이후에 ret으로 현재컴퓨터 포함 해킹할수있는 컴퓨터의 수를 나타냈다.

 

본문

1.문제에 따라서 n,m을 입력받은이후에m번만큼 순회하면서 신뢰하는컴퓨터들을 입력받는다.

2. 이후 백터에 신뢰하는관계를 저장 b->a

3. dfs시행후에 dp[i]번쨰에 저장한다. 이후 max로 최대값을 갱신

4. dp[i] == mx 로 모든 컴퓨터 번호를 오름차순으로 출력한다.