백준) 1325 - 효율적인 해킹

문제 링크 :  https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

문제

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

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

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

입력

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

출력

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

 

풀이

정말 눈물을 흘린 문제다. 막상 풀고 나니까 별거 아닌 기분.. ㅠㅠ

c 로만  문제 풀이를 고집 하가(왜 그런 고집을 부린지는 모르겠다.)  진짜 C++ 공부하고 나서부터 느낀 거지만 접근 하기가 진짜 훨씬 수월 하다. 진짜 1325번 감사합니다.   

나는 DFS 로 구현을 했다. for문을 이용하여 출발 컴퓨터를 1번부터 순차적으로 시작해주었다. 방문한 지역은 다시 방문하지 않도록  visited배열을 이용해 주었고 vector를 이용하여 리스트 형태로 해당 컴퓨터가 신뢰하는 관계를 구현해주 었다. 매번 초기 dfs 가 끝나면 그때의 ans 값이 Max 보다 크면 Max 값을 경신해주어  마지막 출력 시에  Max 인 배열만 출력할 수 있도록 해주었다. 

다음에는 BFS로 구현을 해보아야겠다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
 
vector <int> a[10001];
int tmp[10001];
int visited[10001];
int ans;
int Max;
 
void dfs(int s ) {
 
    int i ;
 
    for( i = 0 ; i< a[s].size() ; i++) {
 
            int y ; 
 
            y = a[s][i];
 
if(visited[y]) continue;
 
            visited[y] =1;
    
            ans++;
            dfs(y);
 
    }
 
}
 
 
int main()
{
    int N , M ;
    cin >> N >> M;
    int i,j;
 
    int x,y;
    for( i =1 ; i <= M; i++) {
        
        cin >> x >> y;
        //x 가 y 를 신뢰한다.
        a[y].push_back(x);
 
    }
 
for( i = 1 ; i<= N ; i++) {
    ans = 0;
    memset(visited,0 , sizeof(visited));
    visited[i] =1;
    dfs(i);
    tmp[i] = ans;
 
    if(Max < ans )
        Max = ans;
 
}
 
 
for(i=1; i<=N; i++) {
 
    if(tmp[i] == Max)
    cout << i <<' ';
 
}
 
    return 0;
}