[그래프 / BOJ 1325 / C++] 효율적인 해킹

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

1325번: 효율적인 해킹

1) 인접 리스트를 선언한다.
2) 자식노드를 순회하는 dfs를 선언한다. 단, int형을 반환한다.
3) 리턴값끼리 비교해가며 최대값을 갱신한다. 단, 최대값이 동일한 경우 해당 노드를 res 배열에 넣어준다.

어렵다..... 고 생각이 들지만 이게 트리 일종이라고 생각하면 어느정도 답이 나온다.

 

나는 바로 인접 리스트를 만들고 dfs를 돌렸다.

 

처음에는 인접 리스트들의 size를 구해서 가장 큰 size를 가진 노드가 답이라고 생각해서 코드를 짜려했는데

잘되지 않았다.

 

우선 그림부터 그려보자!

예제를 그대로 그림으로 그려보면 이런 모습이다. 화살표의 방향이 해킹을 하는 방향이다.

여기서 착각하면 안되는게 신뢰관계라고 해서 B해킹시 A해킹은 맞지만, 그 역(A->B)은 성립되지 안되는 걸 꼭 짚고 가야한다.

나는 그걸 착각해서 고생을 좀 많이했다 ㅠㅠ 문제를 꼭 제대로 읽자. (나만 바보였을지도...^)

 

bfs로 트리를 순회하는데, 여기서 주목해야할 점이 바로 void가 아니라 int형을 반환한다.

 

이것도 이전 트리문제와 비슷한데, 재귀를 돌수록 합이 증가해 결국 최종 리턴값은 자식 노드들의 개수 + 1(자기자신)가 된다!

 

빨강색 숫자는 리턴값들이다.

이렇게 최종적으로 나온 리턴값의 최대값을 구하면 된다! 같을 경우에는, 별도의 배열에 넣어주자.

#include <bits/stdc++.h>

using namespace std;

int N, M, A, B;
vector<int> arr[10001];
int vis[10001], res[10001];

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    for(int i = 0 ; i < M ; i++){
        cin >> A >> B;
        
        arr[B].push_back(A);
    } // 트리 만들기 node는 1부터 N까지.
    
    int mx = 0;
    for(int i = 1 ; i <= N ; i++){
        memset(vis, 0, sizeof(vis));
        res[i] = dfs(i);
        mx = max(res[i], mx);
    } // 트리 순회해서 가장 사이즈가 큰 노드 찾기.
    
    for(int i = 1 ; i <= N ; i++) {
        if(mx==res[i]){cout << i << ' ';}
        
    }
    
}