[BOJ] 백준 16437번 양 구출 작전 (Java)

#16437 양 구출 작전

난이도 : 골드 2

유형 : 트리 / DFS 

16437번: 양 구출 작전

▸ 문제

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

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

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

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

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

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

▸ 입력

첫 번째 줄에 섬의 개수 N (2 ≤ N ≤ 123,456) 이 주어집니다.

두 번째 줄부터 N-1개에 줄에 2번 섬부터 N번 섬까지 섬의 정보를 나타내는 ti, ai, pi (1 ≤ ai ≤ 10^9, 1 ≤ pi ≤ N) 가 주어집니다.

ti가 'W' 인 경우 i번 섬에 늑대가 ai마리가 살고 있음을, ti가 'S'인 경우 i번 섬에 양이 ai마리가 살고 있음을 의미합니다. pi는 i번째 섬에서 pi번 섬으로 갈 수 있는 다리가 있음을 의미합니다.

▸ 출력

첫 번째 줄에 구출할 수 있는 양의 수를 출력합니다.

 

문제 풀이  

22년 카카오 1차 코테 5번 트리문제와 거의 유사한 문제이다. DFS 재귀호출로 인한 트리 후위 순회와 DP를 이용하여 문제를 해결할 수 있다. 문제의 유형을 파악했으면 다음은 주어진 범위를 확인해야 한다. 노드의 최대 갯수는 123,456개이고 각 노드에 저장될 수 있는 양과 늑대의 수는 최대 10^9개이다. dp로 덧셈연산을 하게되면 int범위(2*10^9)를 가볍게 넘게되므로 long으로 다뤄줘야 한다는 것을 유의하자.

 

구현 및 설계

주어진 트리 데이터를 후위 순회하여 바텀업 방식으로 리프노드부터 타고 올라와야한다. 그래서 서브트리의 전체 합(양+늑대)이 늑대의 수가 더 많은 경우 해당 서브트리는 잘라주면 된다. 그러면 구출할 수 있는 양의 최대 수를 구할 수 있다.

 

트리 탐색과정

 

1. 각 노드의 연결되어 있는 도로를 인접리스트 자료구조에 저장한다.  list[p].add(i);
2. 각 노드에 머물러있는 양과 늑대의 수를 dp배열에 양은 양수로, 늑대는 음수로 저장한다. memo[i] = a;
3. 후위 순회를 통하여 리프노드부터 부모노드로 양이 이동한다. dfs(nxt, idx);
   1. 만약 늑대의 수가 더 많을 경우는 제외한다. if(meme[idx]>0)
4. 1번 노드에 도착한 양의 수를 출력한다. sout(memo[1]);

 

풀이 코드 

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

public class Main {

	static List<Integer>[] list; 
	static long[] memo;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		memo = new long[n+1];
		StringTokenizer st;
		for(int i=2; i<n+1; i++) {
			st = new StringTokenizer(br.readLine());
			
			char c = st.nextToken().charAt(0);
			int a = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			
			list[p].add(i);
			if(c=='W') {
				a *= -1;
			}
			memo[i] = a;
		}
		
		dfs(1,-1);
		System.out.println(memo[1]);
	}
	
	static void dfs(int idx, int pa) {
		for(int nxt : list[idx]) {
			dfs(nxt, idx);
		}
		
		if(pa != -1) {
			if(memo[idx]>0) {
				memo[pa] += memo[idx];
			}
		}
	}
}