백준 16437 (양 구출 작전) - java

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

16437번: 양 구출 작전

 

문제

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

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

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

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

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

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

 

유형 : 트리 + 다이나믹 프로그래밍

 

접근 방식

• 트리에서의 다이나믹 프로그래밍 문제이다.
  • 1번 노드 (루트)를 기준으로 DFS 탐색을 한다. 거슬러 올라갈 때 양일 경우 숫자를 반환하는데 늑대를 만난 경우 합하는 과정에서 숫자를 감소시키기 위해 늑대의 숫자를 음수로 저장하였다.
  • 숫자가 0보다 작거나 같아진 경우 그냥 0을 반환하여 숫자의 증감이 일어나지 않게 구현하였다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;

    static ArrayList<Integer>[] graph;
    static char[] what;
    static long[] count;

    static boolean[] v;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        what = new char[n+1]; // 늑대인지 양인지
        count = new long[n+1]; // 살아남은 양
        v = new boolean[n+1]; // 방문 여부

        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=2;i<=n;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            char w = st.nextToken().charAt(0);
            long num = Long.parseLong(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[v].add(i);
            what[i] = w;

            int tmp = 1;
            if(what[i] == 'W'){
                tmp = -1; // 늑대일 경우 음수로 표기
            }
            count[i] = num * tmp; // 양인 경우 양수로 표기
        }

        long result = dfs(1);

        System.out.println(result);
        bf.close();
    }

    static long dfs(int cur){

        v[cur] = true;

        long tmpCount = 0;

        for(int next : graph[cur]){
            if(!v[next]){
                tmpCount += dfs(next);
            }
        }

        count[cur] += tmpCount;

        if(count[cur] < 0)
            return 0l; // 음수일 경우 위로 올려보낼때 0으로 올려보냄 (늑대는 이동하지 않는다)

        return count[cur];
    }
}