백준 16437 : 양 구출 작전

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

16437번: 양 구출 작전

[ 문제풀이 ]

골드 2 난이도 치고는 굉장히 간단한 문제이다. "각 섬에서 1번 섬으로 가는 경로는 유일하다"라는 문장 때문에 모든 섬을 연결한 상태는 그래프가 아닌 트리라는 것을 알 수 있다.

따라서 1번 노드를 기준으로 dfs를 수행하며 말단 노드부터 거슬러 올라오면서 양 or 늑대인 경우를 처리해주면 쉽게 해결할 수 있다.

주의해야 할 점은 정답의 범위가 int 범위를 넘어갈 수 있기 때문에 long 타입으로 받아줘야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int[] vertex;
	static List<Integer>[] edgeList;
	static boolean[] visit;
	
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			N = Integer.parseInt(br.readLine());
			vertex = new int[N + 1];
			edgeList = new ArrayList[N + 1];
			visit = new boolean[N + 1];
			for (int i = 0; i <= N; ++i) edgeList[i] = new ArrayList<>();
			for (int i = 2; i <= N; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String kind = st.nextToken();
				int cnt = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				vertex[i] = kind.equals("S") ? cnt : -cnt;
				edgeList[to].add(i);
			}
			
			bw.write(dfs(1) + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static long dfs(int v) {
		if (edgeList[v].isEmpty()) return vertex[v] > 0 ? vertex[v] : 0;
		
		visit[v] = true;
		long sum = vertex[v];
		for (int nv : edgeList[v]) {
			if (visit[nv]) continue;
			sum += dfs(nv);
		}

		return sum > 0 ? sum : 0;
	}
}