[JAVA] BOJ 백준 16437번 - 양 구출 작전

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

16437번: 양 구출 작전

---

2. 내가 푼 방법

위상정렬 알고리즘을 생각해내면 금방 해결할 수 있는 문제이다.

 

위상정렬은 그래프 상에서 순서가 존재할 때, 먼저 탐색되어야 하는 노드가 존재한다면 이전 노드들을 모두 탐색한 후에 현재 노드를 지날 수 있도록 하는 알고리즘이다. 따라서 자식 노드를 먼저 탐색해야 하는 노드로 설정하고, 자식 노드에서 현재 노드로 들어오는 경로를 카운팅한다. 만약 카운팅한 경로 수가 자식 노드의 개수와 동일해진다면 자식 노드를 모두 방문했다는 뜻이므로 현재 노드를 탐색할 수 있다.

 

양 구출 작전 문제에 위상정렬 알고리즘을 적용해 보면, 각 섬마다 들어오는 양의 수를 알기 위해 리프 노드부터 탐색이 이루어져 1번 섬까지 이동해야 한다. 따라서 더 이상 탐색할 자식 섬이 없을 경우(count[p] == 0), 현재 섬까지 이동할 수 있는 양의 수에 현재 섬에 살고 있는 양/늑대의 수를 더해준다. 만약 늑대의 수가 더 많아 음수가 되어도 늑대는 섬을 이주할 수 없기 때문에, 이주하는 양의 수는 0이라는 것만 주의하면 된다.

public static void solution() {
    for (int i = 1; i <= N; i++) {
        if (count[i] == 0 && !visit[i]) {
            visit[i] = true;
            bfs(i);
        }
    }
}

public static void bfs(int s) {
    Queue<Integer> queue = new ArrayDeque<>();

    move[s] = Math.max(0l, parent[s][1]);
    queue.add(s);

    while (!queue.isEmpty()) {
        int q = queue.poll();

        if (q == 1) break;

        int p = parent[q][0];
        count[p]--;
        visit[p] = true;
        move[p] = Math.max(0l, move[p] + move[q]);

        if (count[p] == 0) {
            move[p] = Math.max(0l, move[p] + (long) parent[p][1]);
            queue.add(p);
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B16437.java

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

class Main {
    static int N;
    static int[][] parent;
    static int[] count;
    static long[] move;
    static boolean[] visit;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        // bfs
        // 위상정렬
        for (int i = 1; i <= N; i++) {
            if (count[i] == 0 && !visit[i]) {
                visit[i] = true;
                bfs(i);
            }
        }
    }

    public static void bfs(int s) {
        Queue<Integer> queue = new ArrayDeque<>();

        move[s] = Math.max(0l, parent[s][1]);
        queue.add(s);

        while (!queue.isEmpty()) {
            int q = queue.poll();

            if (q == 1) break;

            int p = parent[q][0];
            count[p]--;
            visit[p] = true;
            move[p] = Math.max(0l, move[p] + move[q]);

            if (count[p] == 0) {
                move[p] = Math.max(0l, move[p] + (long) parent[p][1]);
                queue.add(p);
            }
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(move[1]+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        parent = new int[N+1][2];
        count = new int[N+1];
        move = new long[N+1];
        visit = new boolean[N+1];

        for (int i = 2; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            String command = st.nextToken();

            int share = ("W".equals(command)) ? -1 : 1;
            int num = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            parent[i][0] = p;
            parent[i][1] = num * share;
            count[p]++;
        }

        br.close();
    }
}

---

4. 결과 및 회고

문제에서 위상정렬 알고리즘을 사용하는 것만 알아차린다면 실제 구현은 쉬운 것 같다.