[ABC226 C] Martial artist

난이도: 539

 

태그

• Depth First Search (깊이 우선 탐색)

 

풀이

1. \( N \)번째 동작을 배우기 위해 배워야 하는 동작들은?

\( N \)번째 동작을 배우기 위해서는, \( A_{N, 1}, A_{N, 2}, \ldots, A_{N, K_N} \)번째 동작을 배워야 합니다.

그런데, 이러한 동작들을 배우기 위해서는 \( A_{A_{N, 1}, 1}, A_{A_{N, 1}, 2}, \ldots, A_{A_{N, 1}, K_{A_{N, 1}}} \)번째 동작 등등을 배워야 합니다.

 

여기서, 동작들을 정점으로, 동작 간의 선후관계를 간선으로 나타내는 그래프를 만들어봅시다.

즉, \( i \rightarrow A_{i, k} \)를 다 만들어봅시다.

 

그럼, \( N \)번째 정점에서 출발해서 도달할 수 있는 모든 정점들은

\( N \)번째 동작을 배우기 위해 직/간접적으로 배워야 하는 동작들을 의미하게 됩니다.

 

2. 그럼, 이 동작들을 모두 배우려면 걸리는 시간은?

우리가 배워야 하는 동작들을 \( B_{1}, B_{2}, \ldots, B_{M} \)이라고 해봅시다.

편의상, \( B_{1} < B_{2} < \ldots < B_{M} = N \)입니다.

 

그럼, \( A_{i, k} < i \)임이 보장되므로 \( B_{1} \)은 항상 배울 수 있습니다.

그 뒤로는, \( B_{2} \)를 항상 배울 수 있게 되고, 그 뒤에는 \( B_{3} \)를 배울 수 있게 되고, ...

이런 식으로 모든 동작들을 순차적으로 배울 수 있게 됩니다.

 

그러니, 문제의 답은 배워야 하는 동작들에 걸리는 시간의 합이 됩니다.

 

코드

ll arr[200020];
vector<int> adj[200020];
 
bool chk[200020];
void dfs(int now){
    chk[now] = 1;
    for (int nxt : adj[now]){
        if (chk[nxt]){ continue; }
        dfs(nxt);
    }
}
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        int k; cin >> arr[i] >> k;
        while (k--){
            int v; cin >> v; adj[i].push_back(v);
        }
    }
    dfs(n);
    ll ans = 0;
    for (int i = 1; i <= n; i++){ ans += chk[i]*arr[i]; }
    cout << ans;
}