백준 16437번 : 양 구출 작전 (C/C++)

<문제>

백준 16437번

 

<풀이>

주어진 문제상황은 DAG이고, 최종 목적지가 1번이다. 따라서 위상 정렬을 적용해볼 수 있다.

 

늑대의 수를 음수로 표현하고, 양의 수를 양수로 표현한다.

문제에서 늑대들은 이동하지 않는다고 했으므로 노드가 양수가 되었을때, 다음 노드로 넘겨주면 된다.

 

<코드>

#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
 
vector<int> g[123457];
ll d[123457];
int inDeg[123457];
 
int main(){
    int n; scanf("%d", &n);
    getchar();
    for(int i = 2; i <=n; i++){
        char t; t = getchar();
        int a, p; scanf("%lld %d", &a, &p);
        getchar();
        g[i].push_back(p);
        d[i] = (t == 'S') ? a : 0-a;
        inDeg[p]++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(inDeg[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
 
 
        for(auto nx : g[x]){
            if(--inDeg[nx] == 0) q.push(nx);
            if(d[x] > 0) d[nx] += d[x];
        }
    }
    printf("%lld", d[1]);
}

<회고>

위상정렬 문제라는 것을 눈치채고 나서는 빨리 풀었으나 위상정렬이라는 것을 알아내는데 시간이 좀 걸린것 같다.