백준 16437 양 구출 작전

16437번: 양 구출 작전

문제

N개의 섬으로 이루어진 나라가 있습니다. 섬들은 1번 섬부터 N번 섬까지 있습니다.

1번 섬에는 구명보트만 있고 다른 섬에는 양들 또는 늑대들이 살고 있습니다.

늘어나는 늑대의 개체 수를 감당할 수 없던 양들은 구명보트를 타고 늑대가 없는 나라로 이주하기로 했습니다.

각 섬에서 1번 섬으로 가는 경로는 유일하며 i번 섬에는 pi번 섬으로 가는 다리가 있습니다. 

양들은 1번 섬으로 가는 경로로 이동하며 늑대들은 원래 있는 섬에서 움직이지 않고 섬으로 들어온 양들을 잡아먹습니다. 늑대는 날렵하기 때문에 섬에 들어온 양을 항상 잡을 수 있습니다. 그리고 늑대 한 마리는 최대 한 마리의 양만 잡아먹습니다.

얼마나 많은 양이 1번 섬에 도달할 수 있을까요?

 

풀이

문제에 친절하게 그림이 그려져 있다.

첫번째 예제

input

4

S 100 3

W 50 1

S 10 1

첫번째 예제의 경우 섬이 4개가 있다. 2번 섬엔 양이 100마리 있고 3번 섬엔 늑대가 50마리, 4번 섬엔 양이 10마리가 있다.

 

양은 2번 섬 -> 3번 섬 -> 1번 섬, 4번 섬 -> 1번 섬으로 갈것이고,

2번섬에서 3번섬을 거쳐갈때,  양 50마리는 3번 섬의 늑대 50마리에게 잡아먹힐 것이고

3번섬에서 1번섬으로 50마리의 양이 갈 수 있다.

 

두번째 예제

input

7

S 100 1

S 100 1

W 100 1

S 1000 2

W 1000 2

S 900 6

두번째 예제의 경우, 양이 1번 섬으로 가는 방법은

7 -> 6 -> 2 -> 1

5 -> 2 -> 1

3 -> 1

이 방법이 있다. ( 4->1 은 늑대는 움직이지 않는다는 조건이 있으므로 x)

 

1. 7 -> 6 -> 2 -> 1 이 방법은 6번 섬에서 늑대가 양보다 많으므로 양이 모두 잡아먹혀서 양은 1번섬에 도착할 수 없다.( 0마리가 도착하는 것이다)

2. 5 -> 2 -> 1 은 양 1100 마리가 도착할 수 있다.

3. 3 -> 1 은 양 100마리가 도착할 수 있다.

나는 이문제를 풀기 위해서 dfs를 썼다.

dfs로 리프 노드까지 갔다가 리프 노드 부터 다시 루트 노드로 올라올때 올라올 수 있는 양을 계산해 주었다.

 

#include <iostream>
#include <vector>
#define MAX 123457
 
using namespace std;
 
vector<int> graph[MAX];
 
long long dfs(vector<pair<char, int>> &island,int cur)    // 계산과정에서 int 범위를 넘길 수 있으므로 long long으로 계산해준다.
{
    int s = graph[cur].size();
    if (s == 0) {
        if (island[cur].first == 'S') {
            return island[cur].second;
        }
        else {
            return  0;
        }
    }
    long long ret = 0;
    for (int i = 0; i < s; ++i) {
        int next = graph[cur][i];
        ret += dfs(island, next);    // 마지막 섬까지 dfs 호출
    }
    if (island[cur].first == 'W') {    // 늑대면 ret -= 늑대의 수
        ret -= island[cur].second;
        if (ret < 0) ret = 0;    // 늑대가 더 많으면 양은 0마리
    }
    else {
        ret += island[cur].second;
    }
    return ret;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<pair<char, int>> island(N + 1);
    island[1] = make_pair('S', 0);
    for (int i = 2; i <= N; ++i) {
        char t;
        cin >> t;
        int a, p;
        cin >> a >> p;
        island[i] = make_pair(t, a);
        graph[p].push_back(i);
    }
    cout << dfs(island, 1) << "\n";
 
    return 0;
}