[JAVA] BOJ 백준 1005번 - ACM Craft

목차

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

---

1. 문제

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

---

2. 내가 푼 방법

연결리스트를 사용해서 단방향 그래프를 그려주었다. 이때 그래프 방향은 더 늦게 지어지는 건물에서 더 먼저 지어져야 하는 건물 방향으로 연결해 주었다.

for (int k = 0; k < K; k++) {
    st = new StringTokenizer(br.readLine());
    int v1 = Integer.parseInt(st.nextToken());
    int v2 = Integer.parseInt(st.nextToken());

     list[v2].add(v1);
}

 

bfs 함수를 통해 정답을 도출해 냈는데, while문을 통해 BFS 알고리즘을 구현하는 것은 기본이되 checkLast 배열과 countMax 배열을 사용하여 비용을 계산했다. 

checkLast 배열은 queue에 동일 건물이 들어있을 때 확인할 수 있는 배열이고,

countMax 배열은 해당 건물까지 오기까지 걸리는 최고 시간 비용을 담는 배열이다.

 

그래프 방향은 당연하게 최종 건물에서 초기 건물까지 가야 한다. 따라서 아래 코드를 보면 인자로 받은 W를 먼저 큐에 넣어주면서 시작한다. 위에서 말했던 두 배열을 적절히 사용하면서 아래 코드가 완성되고, 지어야 할 선수 건물이 없을 경우에 초기 건물까지 왔다는 것이므로 if (list[idx].size() == 0) 일 경우에 reuslt에 최고값을 넣어주면 된다.

public static int bfs (List<Integer>[] list, int[] cost, int W) {
    int result = 0;

    int[] checkLast = new int[list.length+1]; // 0일 경우, 선수 건물 짓기 (= 무한루프 피하기)
    int[] countMax = new int[list.length+1]; // 현재 건물을 짓기까지 걸리는 최고 시간 비용

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(W, cost[W]));
    checkLast[W]++;

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();
        int idx = tuple.idx;
        int count = tuple.count;

        checkLast[idx]--;
        countMax[idx] = Math.max(countMax[idx], count);

        if (checkLast[idx] != 0) continue;

        for (Integer i : list[idx]) {
            checkLast[i]++;
            queue.add(new Tuple(i, countMax[idx] + cost[i]));
        }

        if (list[idx].size() == 0) result = Math.max(result, countMax[idx]);
    }

    return result;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B1005.java

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

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine()); // 테스트케이스 개수

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 건물 개수
            int K = Integer.parseInt(st.nextToken()); // 규칙 개수

            int[] cost = new int[N+1]; // 건물 당 드는 비용(시간)
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                cost[i] = Integer.parseInt(st.nextToken());
            }

            List<Integer>[] list = new ArrayList[N+1]; // 연결된 건물
            for (int i = 1; i <= N; i++) {
                list[i] = new ArrayList<>();
            }

            for (int k = 0; k < K; k++) {
                st = new StringTokenizer(br.readLine());
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                list[v2].add(v1);
            }

            int W = Integer.parseInt(br.readLine()); // 최종 건물

            bw.write(bfs(list, cost, W)+"\n");
        }

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

    public static int bfs (List<Integer>[] list, int[] cost, int W) {
        int result = 0;

        int[] checkLast = new int[list.length+1]; // 0일 경우, 선수 건물 짓기 (= 무한루프 피하기)
        int[] countMax = new int[list.length+1]; // 현재 건물을 짓기까지 걸리는 최고 시간 비용

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(W, cost[W]));

        checkLast[W]++;

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int idx = tuple.idx;
            int count = tuple.count;

            checkLast[idx]--;
            countMax[idx] = Math.max(countMax[idx], count);

            if (checkLast[idx] != 0) continue;

            for (Integer i : list[idx]) {
                checkLast[i]++;
                queue.add(new Tuple(i, countMax[idx] + cost[i]));
            }

            if (list[idx].size() == 0) result = Math.max(result, countMax[idx]);
        }

        return result;
    }

    public static class Tuple {
        int idx;
        int count;

        public Tuple (int idx, int count) {
            this.idx = idx;
            this.count = count;
        }
    }
}

---

4. 결과 및 회고

처음에는 깊이를 기준으로 최고 비용을 카운팅 해주었는데, 그 경우에는 깊이가 더 깊어도 더 작은 값을 가질 수 있는 반례가 생겼다. 따라서 각 정점에 도달하기까지 가지는 최고 비용을 계산해주는 방법으로 변경하여 풀었다.