Cooper's devlog

[문제 설명]

 이번 문제는 '양 구출 작전 '입니다.

문제를 간략히 설명하자면

• 각각의 섬들은 연결된 상태로 존재한다.
• 1번을 제외한 섬에는 양 혹은 늑대가 산다.
• 양을 싣고 이동하는 중에 늑대가 있는섬을 만나면 늑대는 양을 잡아먹는다.(늑대 1마리당, 양 1마리)
• 1번 섬으로 구출할 수 있는 양의 수를 찾는다.

[문제 접근 방법]

문제의 내용에 '각각의 섬들은 연결된 상태로 존재한다.'

이 문구를 확인하고 트리 구조로 문제를 접근해야겠다고 생각했고

각 LeafNode들에서 출발해서 1번 섬에 도달할 때까지 양들이 살아남는 경우를 구하는 것이었습니다.

그러기 위해서는 순회 방법 중 후위순회(postOrder)이 적합하다고 생각했습니다.

먼저 문제 풀이 방식을 설명하면

<후위순회 선택 이유>

리프노드에서 출발해서 상위 노드로 올라가면서 연산을 처리한다는 점이었습니다.

구체적으로 설명하자면 아래와 같은 유사성이 있었습니다.

• 가장 멀리 있는 섬에서 출발해 다음 섬에서 양과 늑대에 대한 결과를 처리 후, 가장 상위 노드인 1번 섬 도달
• 최하위 노드 연산 결과를 상위 노드까지 연산을 끌고 오는 방식
• 좌측 서브 트리 결과와 우측 서브 트리 결과를 루트 노드와 비교해서 연산을 진행하는 방식

<트리 구조 구현>

ArryaList을 요소로 한 배열을 통해 구현을 했습니다.

배열의 인덱스는 섬의 번호를 의미하고, ArrayList의 요소들은 섬과 연결된 다른 섬들의 번호들을 저장하는 방식으로 접근했습니다.

[code]

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

class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

    static ArrayList<Integer>[] nodes;
    static int[] score;
    static char[] animal;

    public static void main(String[] args) throws IOException {
        int numberOfNodes = Integer.parseInt(br.readLine());

        nodes = new ArrayList[numberOfNodes + 1];
        animal = new char[numberOfNodes + 1];
        score = new int[numberOfNodes + 1];

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

        for (int Index = 2; Index < numberOfNodes + 1; Index++) {
            st = new StringTokenizer(br.readLine());

            char NodeAnimal = st.nextToken().charAt(0);
            int amount = Integer.parseInt(st.nextToken());
            int nextNode = Integer.parseInt(st.nextToken());

            animal[Index] = NodeAnimal;
            score[Index] = amount;
            nodes[nextNode].add(Index);
        }


        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 (animal[node] == 'S') {
            return sum + score[node];
        } else {
            return (sum - score[node] >= 0) ? sum - score[node] : 0;
        }
    }
}

0. 구성 요소 설명

    static ArrayList<Integer>[] nodes;			//다음 노드들의 정보를 담는 ArrayList
    static int[] score;					//점수들 담는 배열
    static char[] animal;				//동무렝 대한 정보를 담는 배열

1. postOrder를 이용한 탐색 및 결과 도출

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

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

        if (animal[node] == 'S') {
            return sum + score[node];
        } else {
            return (sum - score[node] >= 0) ? sum - score[node] : 0;
        }
    }

1. 먼저 해당 노드의 자식 노드들을 탐색합니다.

2. 만약 존재한다면 자식 노드들 탐색해서 자식 노드들을 더욱 탐색하도록 합니다.

3. 그리고 리프노드에 도달하게 된다면 아래 조건문을 연산합니다.

• 만약 양(S)일 경우, 합에 양의 수를 추가하고,
• 만약 늑대(W)일 경우, 합산에서 늑대의 수 만큼 제거하도록 합니다.

[결과]

결과를 확인해보면 정답인 것을 확인해볼 수 있습니다.

아쉬운 점이 있다면 섬에 대한 정보를 독립적으로 관리했다는 점입니다.

기회가 된다면 class로 설계해 정보를 한번에 관리하고 결과를 도출할 수 있는 방법으로도 포스팅하도록 하겠습니다.

봐주셔서 감사합니다:)