[Java] 16437번 양구출작전

1. 문제 링크

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

1-1 문제 요약

: 1번섬에 올 수 있는 양의 수

2. 해결 방법 생각해보자 ..

후위순회 트리

3. 코드

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static List<Integer>[] BridgeInfo;
    static long[] AnimalInfo;

    public static void main(String[] args) throws IOException {
        // 값 입력받기 -->
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        BridgeInfo = new ArrayList[N+1];
        AnimalInfo = new long[N+1];
        for(int i=0;i<N+1;i++){
            BridgeInfo[i] = new ArrayList<Integer>();
        }

        for(int i=2;i<N+1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            char animal = st.nextToken().charAt(0);
            int amount = Integer.parseInt(st.nextToken());
            int bridge = Integer.parseInt(st.nextToken());
            
            BridgeInfo[bridge].add(i);
            if(animal == 'W'){
                amount *= -1 ;
            }
            AnimalInfo[i] = amount;
        }
        //<--

        dfs(1,-1);
        System.out.println(AnimalInfo[1]);
    }

    public static void dfs(int Now, int Before){

        for(int next: BridgeInfo[Now]){
            dfs(next,Now);
        }
        if(Before != -1){
            if(AnimalInfo[Now]>0){
                AnimalInfo[Before] += AnimalInfo[Now];
            }
        }

    }

}