[백준] 16437 양 구출 작전 - 트리(Tree) + DFS(깊이우선탐색) JAVA

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

코드설명

트리(Tree) + DFS(깊이우선탐색) 를 활용하는 문제입니다.

 

트리 루트노드에서 시작하여 DFS를 활용하여 맨 아래 노드부터 하나씩 계산하며 올라오도록 합니다.

 

고민했던점들을 정리해보면, 

맨 아래에서 올라오면서 처리하려고하였는데, 그렇게 할경우 맨 아래 노드가 무엇인지 계산하기 힘들었습니다.

그대신에, simulate 재귀 호출을 통해 자식 노드로 이동한뒤 결과값을 반환하며 값을 누적시키고, 최종적으로 부모 노드로 올라가면서 결과를 반환합니다.

 

Node값으로 데이터를 모두 가져가면서 처리하려고하였는데, 배열로 처리하는것이 더 편하다고 느껴졌습니다.

 

늑대, 양의 값의 범위가 1 ≤ ai ≤ 10^9 라는 조건이 존재하기에  long형으로 처리하여야 범위가 안전합니다.

만약 long형을 사용하지 않을경우 10^9 * 123456 으로 범위를 초과할 수 잇습니다.  

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static long answer = 0;
	public static int[][] arr;
	public static int[][] map;
	public static int[] target;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static char[] animalKind;
	public static int[] amount;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Integer>());
    	}
    	
    	animalKind = new char[N+1];
    	amount = new int[N+1];
    	for(int i=2; i<=N; i++) {
    		st = new StringTokenizer(br.readLine());
    		char t = st.nextToken().charAt(0);
    		int a = Integer.parseInt(st.nextToken());
    		int p = Integer.parseInt(st.nextToken());
    		animalKind[i] = t;
    		amount[i] = a;
    		
    		graph.get(p).add(i);
    	}
    	
    	answer = simulate(1);
    	
    	System.out.println(answer);
	}
	
	
	
	public static long simulate(int nodeIdx) {
 
		long result = 0;
		
		for(int i=0;i<graph.get(nodeIdx).size(); i++) {
			int toChild = graph.get(nodeIdx).get(i);
			result += simulate( toChild );
		}
		
		if( animalKind[nodeIdx] == 'S') {
			return result + amount[nodeIdx];
		}
		else if( animalKind[nodeIdx] == 'W') {
			return result - amount[nodeIdx] < 0 ? 0 : result - amount[nodeIdx];  
		}
		
		return result; //마지막에만 여기까지 옵니다.
	}
	
}