백준 1325번 효율적인 해킹

효율적인 해킹 

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

5 초

256 MB

27608

5060

3348

20.602%

문제

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

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

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

입력

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

출력

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>

using namespace std;

int check[10001]={0,};

int func(int num, vector<int> v[]){
    queue<int> q;
    int cnt=1;
    check[num]=1;
    q.push(num);
    
    while(!q.empty()){
        int front = q.front();
        q.pop();
        for(int i=0; i<v[front].size(); i++){
            if(!check[v[front][i]]){
                cnt++;
                check[v[front][i]] = 1;
                q.push(v[front][i]);
            }
        }
        
    }
    return cnt;
}
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    int MAX = 0;
    
    cin >> n >> m;
    vector<int> v[n+1];
    vector<int> ans;
    for(int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        v[b].push_back(a);
    }
    for(int i=1; i<=n;i++){
        memset(check, 0, sizeof(check));
        int temp = func(i,v);
        if(MAX <temp){
            MAX = temp;
            ans.clear();
            ans.push_back(i);
            
        } else if(MAX == temp){
            ans.push_back(i);
        }
        
    }
    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << ' ';
    }
    return 0;
}

번 문제는 예전에 한번 DFS로 푼적이 있는 문제였다. 그래서 이번엔 BFS로 풀어보았다.

각 컴퓨터마다 연결되어있는 컴퓨터들의 수를 세어 저장하고 이것을 이전 최댓값과 비교해 같으면 정답배열(ans)뒤에 index를 저장하고, 최댓값보다 크면 정답배열을 초기화한 후 해당 인텍스를 저장해준다