[백준 16437] 양 구출 작전 (C++)

문제 링크: www.acmicpc.net/problem/16437

16437번: 양 구출 작전

1. 주의할 점

- 모든 섬에 양이 최대치로 존재 -> 합해지는 과정에서 Int의 범위를 벗어날 수 있다

 

2. 구현

- 위상정렬의 풀이법으로 접근했다

- Info 구조체를 통해 해당 지점을 도착지점으로 설정한 섬의 수(Conn), 다음 섬으로 연결된 곳(To), 생물의 수(Val)를 나타낸다

- 섬에 늑대가 존재하면, 생물의 개수를 음수로 저장한다.

- Info의 성격에 맞게 Arr[] 배열에 값을 저장하며, 섬이 트리형태로 구성되어 있다고 생각하며 Leaf를 Queue에 넣는다(Leaf 구별법: Arr[i].conn==0)

- Queue를 계속해서 돌리며, 현재 섬 기준으로 다음 섬으로 넘어갈 때, 늑대가 양을 다 잡아먹지 않았다면(Val >= 0) 다음 섬으로 Val만큼 넘겨주며, 다음 섬의 Conn를 --해준다.

- 다음 섬의 Conn이 0이라면(Leaf에서부터 역으로 올라가며, 해당 지점 밑으로 모두 검사했다면) 다음 섬을 큐에 넣어주고 위의 작업을 반복한다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info{
    int conn,to;        //이쪽으로 건너는 단뱡향 수,  다음 섬으로 연결된 곳
    long long val;      //생물의 수
};
info tmp;
int num,to;
long long val;
info arr[130000];
long long result=0;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> num;
    char c;
    for(int i=2;i<=num;i++){
        cin>>c>>val>>to;
        if(c=='W') val = -val;      //늑대인 경우, -
        arr[i].to = to;
        arr[i].val = val;
        arr[to].conn++;
    }
    queue<int> q;
    for(int i=2;i<=num;i++){
        if(arr[i].conn==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int cidx = q.front();
        q.pop();
        int next = arr[cidx].to;
        long long cv = arr[cidx].val;
        if(cv>0)    arr[next].val+=cv;        //늑대만 남은 경우, 넘기지 않음
        arr[next].conn--;
        if(arr[next].conn==0) q.push(next);
    }
    cout << arr[1].val;
    return 0;
}