백준 - 16437번

 

풀이

 

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Iterator;

import java.util.LinkedList;

 

public class Main {

 

      static long[] wolf; // 늑대 개수 배열

      static long[] sheep; // 양 개수 배열

      static LinkedList<Integer>[] list; // 각 섬의 연결 리스트

      static boolean[] visited; // 방문 배열

 

      public static void main(String[] args) throws IOException{

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String[] arr;

            String str = br.readLine();

            int num = Integer.parseInt(str);

            wolf = new long[num+1]; // 늑대 개수 배열 초기화

            sheep = new long[num+1]; // 양 개수 배열 초기화

            list = new LinkedList[num+1]; // 섬 연결 리스트 초기화

            visited = new boolean[num+1]; // 방문 배열 초기화

            for (int i = 0; i <= num; i++) { // 섬 연결 리스트의 리스트 생성

                  list[i] = new LinkedList<Integer>();

            }

 

            // 입력받기

            for(int i=2; i<num+1; i++){

                  str = br.readLine();

                  arr = str.split(" ");

                  if("W".equals(arr[0])){

                        wolf[i] = Long.parseLong(arr[1]);

                  }else{

                        sheep[i] = Long.parseLong(arr[1]);

                  }

                  list[Integer.parseInt(arr[2])].add(i);

            }

            System.out.println(Move(1));

      }

 

      // 깊이 우선 탐색 

      private static long Move(int a){

            visited[a] = true; // 해당 섬 방문

            long countSheep = sheep[a]; // 해당 섬의 양 개수 카운팅

            long countWolf = wolf[a]; // 해당 섬의 늑대 개수 카운팅

            Iterator<Integer> iter = list[a].listIterator();

            while (iter.hasNext()) { 

                  int nextArea = iter.next();

                  if(!visited[nextArea]) {

                        countSheep += Move(nextArea);

                  }

            }

            if(countSheep - countWolf > 0) { // 양 수가 늑대 수보다 많을 경우

                  countSheep -= countWolf;

            }else { // 늑대 수가 양 수보다 많을 경우

                  countSheep = 0;

            }

            return countSheep;

      }

}