[백준] 16437번. 양 구출 작전(JAVA)

문제

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

---

플이(32분)

import java.io.*;
import java.util.*;

public class Main {

    static List<Integer>[] tree;  // 트리 구조 표현 (인접 리스트)
    static long[] animalCount;   // 각 노드에 있는 양 또는 늑대 수 (양: 양수, 늑대: 음수)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCount = Integer.parseInt(br.readLine());  // 총 노드 수 (1번이 루트)

        tree = new ArrayList[nodeCount + 1];
        for (int i = 1; i <= nodeCount; i++) {
            tree[i] = new ArrayList<>();
        }

        animalCount = new long[nodeCount + 1];

        for (int child = 2; child <= nodeCount; child++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char type = st.nextToken().charAt(0);  // 'S' 또는 'W'
            int count = Integer.parseInt(st.nextToken()); // 개체 수
            int parent = Integer.parseInt(st.nextToken()); // 부모 노드

            // 트리 연결
            tree[parent].add(child);

            // 동물 개수 저장 (늑대는 음수로 저장)
            animalCount[child] = (type == 'W') ? -count : count;
        }

        dfs(1);  // 루트 노드부터 후위 순회 시작
        System.out.println(animalCount[1]);  // 최종적으로 루트에 남는 양의 수 출력
    }

    // 후위 순회 DFS
    static void dfs(int current) {
        for (int child : tree[current]) {
            dfs(child);  // 자식 먼저 탐색
            if (animalCount[child] > 0) {
                animalCount[current] += animalCount[child];  // 자식 노드의 양을 현재 노드로 전달
            }
        }
    }
}

---

문제 풀이 전략

 

dfs후위 탐색을 하면 되는 것을 직접 트리에 대해 설정을 해주려고 하다가 생각보다 오랜 시간이 걸렸다.

 

후위 탐색을 통해 하단에서부터 올라오며 양과 늑대의 수를 체크해 주는 방식으로 문제 풀이를 진행했다.

양이 있는 경우에만 올려주고, 늑대가 존재하는 경우에는 무시하는 방식으로 했다.

-> 이때도 굳이 늑대에 대한 복잡한 연산을 진행하는 것이 아닌 0보다 큰 경우에만 위로 올리며 + 해주면 된다. 그럼 자연스럽게 늑대와 비교가 된다.