백준 1325번 - 효율적인 해킹

https://www.acmicpc.net/problem/1325

방향성이 있는 연결형 그래프 문제이다.

그림으로 위의 보기를 이해하면 다음과 같다.

이때 1번과 2번은 각각 3,4,5번 컴퓨터를 해킹할 수 있고

3번은 4,5번 컴퓨터를

4,5번은 자기 자신 이외에는 해킹할 수 없다.

이때 중요한 것은 각각의 컴퓨터를 몇번 호출했냐로 해킹할 수 있는 컴퓨터의 개수를 구할 수 있다.

1번은 (1,3,4,5)

2번은 (2,3,4,5)

3번은 (3,4,5)

4번은 (4)

5번은 (5)

이렇게 생각하면 1번과 2번 컴퓨터가 총 4개의 컴퓨터 해킹이 가능해서

답이 된다.

중요한 것은 방문했다는 visited와 몇 번 호출됐다는 hacking라는 변수를 따로 두어서

visited는 매 번 리셋해줘야 하지만

hacking는 호출 될 때 마다 값을 더해줘야 한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N,M;
vector<int> graph[10001];
vector<int> visited; //방문 유무
vector<int> hacking; //각각의 컴퓨터 번호마다 해킹할 수 있는 컴퓨터 개수
 
int ans=0; //가장 많이 해킹할 수 있는 컴퓨터 개수
 
void dfs(int node){
    
    hacking[node]++;
    ans=max(ans,hacking[node]);
    
    for(int i=0;i<graph[node].size();i++){
        
        int next_node=graph[node][i];
        if(!visited[next_node]){
            visited[next_node]++;
            dfs(next_node);
        }
    }
}
int main(){
    
    scanf("%d %d",&N,&M);
    
    int s,e;
    for(int i=0;i<M;i++){
        scanf("%d %d",&s,&e);
        graph[s].push_back(e);
    }
    
    hacking=vector<int> (N+1,0);
    
    for(int i=1;i<=N;i++){
        visited=vector<int> (N+1,0); //방문 초기화
        
        visited[i]++;
        dfs(i);
    }
    
    for(int i=1;i<=N;i++){
        if(hacking[i]==ans){
            printf("%d ",i);
        }
    }
    return 0;
}