[백준] 16437: 양 구출 작전

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

16437번: 양 구출 작전

해당 문제는 DFS, BFS 유형 문제로 출제되어있으나 사실 풀다보면 위상정렬이 적합할 것 같아서 위상정렬로 풀었다.

왜냐하면 하나의 노드의 parent가 하나라는 점이 위상정렬을 가능케하였고, child 노드를 탐색한 후에 parent 노드를 탐색할 수 있었기 때문이다. 물론 이러한 특징들이 있어도 DFS로도 풀수 있는 문제이긴 하다.

child의 양 수를 모두 수합한 다음 현재의 양 수랑 합치거나 늑대수를 빼면 된다.

 

그런데 다 풀어놓고 계속 11%에서 실패가 떠서 난감한 상황에서 코드를 다시 보다가 어디서 잘못 코드를 만들었는지 알아차렸다.

 

현재 island에서 다음 island인 to로 양을 이동시킬 때 to의 양 수가 음수가 되면 0으로 처리해버렸다.

사실 다른 child island가 고려되지 않은 상태라서 그렇게 성급하게 처리하면 안된다.

그래서 현재 Island를 이동기준으로 삼고 있으니, 현재 island가 음수값이 나와서야 음수는 버리는 형태를 취해야 한다.

기준을 명확하게 하자!

/**
 * https://www.acmicpc.net/problem/16437
 */

#include <iostream>
#include <queue>
#include <map>
using namespace std;
long long sheeps[123457];
int indegree[123457] = {0};
map<int, int> islands;
queue<int> q;
int n;
int main() {
    cin >> n;
    for(int i = 2;i <= n;i++) {
        char t;
        long long a, p;
        cin >> t >> a >> p;
        indegree[p]++;
        islands[i] = p;
        if(t == 'S') {
            sheeps[i] = a;
        }
        else {
            sheeps[i] = -1 * a;
        }
    }

    for(int i = 1;i <= n;i++) {
        if(indegree[i] == 0) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int island = q.front();
        q.pop();
        if(island == 1) {
            break;
        }
        // 주의! island에 늑대만 남은 경우만 안 넘기면 된다. 즉 현재 섬인 island 중심 고려
        // 추후 to에 다른 island에서 넘어오는 경우도 고려해야함
        int to = islands[island];
        // 늑대가 업는 경우
        if(sheeps[island] > 0) {
            sheeps[to] = sheeps[island] + sheeps[to];
        }
        if(--indegree[to] == 0) {
            q.push(to);
        }
    }

    cout << sheeps[1] << '\n';
}