[백준 1325] 효율적인 해킹

0. 제목

• 백준 1325 효율적인 해킹
• BOJ 1325 효율적인 해킹
• C++ 1325 효율적인 해킹

---

1. 문제

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

---

2. 풀이

• 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 것이 문제이다.
• dfs를 사용하여 연결되어 있는 컴퓨터의 수를 센다.
• 각 컴퓨터를 시작점으로 dfs를 시행하여 컴퓨터 수를 세고 그것을 depth배열에 담는다.
• depth배열의 원소 중 최댓값을 구한다.
• depth배열의 원소 값 중 최댓값과 같은 값을 가지고 있는 index들을 순서대로 출력한다.

---

3. 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> v[10001];
int visited[10001];
int cnt;
 
void dfs(int x){
    if(visited[x]) return;
    visited[x] = true;
    cnt++;
    for(int i = 0; i < v[x].size(); i++){
        int y = v[x][i];
        dfs(y);
    }
}
 
int main(int argc, const char * argv[]) {
    int N, M;
    cin >> N >> M;
    
    int a, b;
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        v[b].push_back(a);
    }
    
    int depth[10001];
    for(int i = 1; i <= N; i++){
        memset(visited, 0, sizeof(visited));
        cnt = 0;
        dfs(i);
        depth[i] = cnt;
    }
    
    int max = 0;
    for(int i = 1; i <= N; i++){
        if(max < depth[i])
            max = depth[i];
    }
    
    for(int i = 0; i <= N; i++){
        if(max == depth[i])
            cout << i <<' ';
    }
        
    
    return 0;
}