[BOJ] 16437 - 양 구출 작전

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

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

16437번: 양 구출 작전

난이도: 골드 3

사용언어: JAVA

 

풀이

이 문제는 트리 형태의 데이터 구조를 가진다는 점만 잘 이용하면 쉽게 해결할 수 있습니다.

 

트리의 순회 방법 중 후위 순회를 사용하면 트리의 Leaf Node부터 Root Node까지 차례로 올라오면서 남아있는 늑대의 수와 올라올 수 있는 양의 수를 쉽게 계산할 수 있습니다.

 

즉, DFS를 통해 Root Node인 1번 섬으로부터 출발하여 Leaf Node에 도달하면 해당 섬에 존재하는 양 또는 늑대의 수를 이용해 부모 노드에 반영시키는 형태로 구현을 했습니다. 해당 섬에 양이 존재하면 부모 노드로 올려줘서 부모 노드의 양 또는 늑대와 계산하면 되겠죠?

 

또한, 저는 각 섬에 대해 늑대의 수는 음수로 표현하고, 양의 수는 양수로 표현하여 계산을 쉽게 할 수 있도록 했습니다.

 

더 자세한 설명은 코드에 주석으로 첨부하겠습니다.

 

import java.util.*;
import java.io.*;
 
public class Main {
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>(); // DFS를 위한 2차원 ArrayList
    static int N;
    static long[] animal_number_arr; // 각 섬에 남아있는 늑대 또는 양의 수 (늑대는 음수, 양은 양수로 표현)
 
    public static void dfs(int now, int parent) { // now: 현재 섬의 번호, parent: 현재 섬의 부모 노드 
        int next;
 
        for (int i = 0; i < list.get(now).size(); i++) { // 현재 섬의 자식 노드를 모두 탐색
            next = list.get(now).get(i);
 
            dfs(next, now); // 자식 노드로 DFS 수행
        }
 
        // 모든 자식 노드를 탐색한 뒤,
        if (animal_number_arr[now] > 0) { // 현재 섬이 양이 있는 섬이라면
            animal_number_arr[parent] += animal_number_arr[now]; // 부모 노드로 양을 보냄
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        N = Integer.parseInt(br.readLine());
        animal_number_arr = new long[N + 1];
 
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
 
        for (int i = 2; i < N + 1; i++) {
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            char animal_char = st.nextToken().charAt(0); // 'S' or 'W'
            long count_of_animal = Integer.parseInt(st.nextToken()); // 양 또는 늑대의 수
            int parent = Integer.parseInt(st.nextToken()); // 부모 노드
 
            list.get(parent).add(i); 
            if (animal_char == 'S') { // 양이면 양수로 표현
                animal_number_arr[i] = count_of_animal;
            } else { // 늑대면 음수로 표현
                animal_number_arr[i] = count_of_animal * -1;
            }
        }
 
        dfs(1, 0);
 
        bw.write(String.valueOf(animal_number_arr[1]));
        bw.flush();
        bw.close();
        br.close();
    }
}