[BOJ] 16437. 양 구출 작전 - Java

백준 16437 문제

풀이 과정

처음에는 그래프 문제라고 생각했고, 깊이 우선 탐색을 해야한다고 생각해서 깊이 우선으로 방문하는 코드를 짰다. 가장 끝 정점을 알고 그 부분부터 시작하면서 양을 만나면 더해주고, 늑대를 만나면 빼주는 코드로 짰지만 맞지 않았다.

트리를 통해 풀었더니 제대로 된 답을 낼 수 있었다.

해당 문제는, 어떠한 섬에서도 1번 섬으로 가는 경로가 유일하기 때문에 가장 끝 노드인 자식 노드부터 차례대로 늑대, 양의 개수를 누적하면서 1번까지 오면 결과가 나올 수 있는 문제이다. 따라서 트리 자료 구조를 이용하면 되고, postOrder(후위 순회) 방식을 이용하면 쉽게 풀 수 있다.

트리의 순회

• 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문 (Root → Left → Right)
• 중위 순회(inorder traverse) : Left → Root → Right
• 후위 순회(postorder traverse) : Left → Right → Right (뿌리를 가장 나중에 방문한다.)

해당 문제를 풀 때 주의해야 할 부분이 하나 더 있는데, 섬의 개수인 N의 범위가 2 ≤ N ≤ 123456 이고, 양 또는 늑대의 수를 나타내는 a의 범위는 1 ≤ a ≤ 10^9 이기 때문에, 1까지 왔을 때의 최대 수가 123455 x 10^9 이기 때문에 int로 표현할 수 있는 범위를 초과한다. 따라서 양과 늑대를 세는 변수 및 배열은 long 형으로 선언하여 풀었다.

풀이 코드

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

/**
 * <문제 요약>
 * 구해야 하는 것: 구할 수 있는 양의 수
 * 제약 사항: 2<=N<=123456
 * 문제 유형: 트리 
 * 요구 개념: 트리 / 후위순회
 * 
 */
public class BOJ_Gold2_16437_양구출작전 {

    static int N;
    static long w[], s[];
    static long count;
    static ArrayList<Integer>[] nodes;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        w = new long[N+1];
        s = new long[N+1];

        nodes = new ArrayList[N+1];

        for (int i = 1; i <= N; i++) {
            nodes[i] = new ArrayList<Integer>();
        }

        StringTokenizer st=null;
        for (int from = 2; from <= N; from++) {
            st = new StringTokenizer(in.readLine(), " ");
            String type = st.nextToken();
            long cnt = Long.parseLong(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            if(type.equals("S")) {
                s[from] = cnt;
            } else {
                w[from] = cnt;
            }

            nodes[to].add(from);
        }

        System.out.println(postOrder(1));
    }

    private static long postOrder(int node) {
        long sum = 0;

        //left -> Right -> Root
        for(int next : nodes[node]) {
            sum += postOrder(next);
        }

        if(w[node] != 0 && s[node] == 0) {
            return w[node] >= sum ? 0 : sum-w[node]; 
        } else {
            return sum += s[node];
        }

    }
}