[백준] 1516번 게임 개발 (JAVA)

문제

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

1516번: 게임 개발

 

설명

어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다.
여러 개의 건물을 동시에 지을 수 있다.

건물을 짓는데 우선순위가 있으므로 이는 DAG로 나타낼 수 있다. 

먼저 건물을 짓는데 걸리는 시간과 후행자로 가지는 건물 번호 리스트를 저장할 Build 클래스를 만든다.

class Build {
    int time;
    ArrayList<Integer> successor;

    public Build(int time, ArrayList<Integer> successor) {
        this.time = time;
        this.successor = successor;
    }

    public void setTime(int time) {
        this.time = time;
    }

    public ArrayList<Integer> getSuccessor() {
        return successor;
    }
}

BFS를 이용한 위상정렬을 통해 해당 문제를 풀이하면 된다.

해당 건물의 in-degree를 저장할 inDegree 배열과 현재 지을 건물을 저장할 queue를 만든다. 

그리고 각각의 건물이 완성되기까지의 최소 소요시간을 저장할 minTime 배열도 만든다.

입력된 건물 번호는 현재 건물의 선행자이므로 입력된 건물 번호의 후행자 리스트에 현재 건물을 저장한다.

in-degree가 0인 건물은 큐에 추가한다.

int[] inDegree = new int[N + 1];
int[] minTime = new int[N + 1];
Queue<Build> queue = new LinkedList<>();

for (int i = 1; i <= N; i++) {
    st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken());
    buildings[i].setTime(t);
    minTime[i] = t;

    int temp;
    while ((temp = Integer.parseInt(st.nextToken())) != -1) {
        // temp를 선행자로 가지는 건물 번호를 저장한다.
        buildings[temp].getSuccessor().add(i);
        inDegree[i]++;
    }

    if (inDegree[i] == 0)
        queue.offer(buildings[i]);
}

큐가 비어있을 때까지 다음 과정을 반복한다.

큐에서 하나를 빼내서 빼낸 건물 번호의 후행자를 탐색한다.

해당 후행자에 대해 (건물을 짓는데 걸리는 최소 시간)과 (건물 짓는데 필요한 시간 + 현재까지 건물 짓는데 걸린 시간)을 비교해서 minTime 배열을 최신화시킨다.

그리고 in-degree를 1 감소시킨 뒤 값이 0이라면 큐에 넣는다.

이때, 해당 건물을 짓기까지 소요된 시간으로 최신화해주어야 한다.

static void getMinTime() {
    while (!queue.isEmpty()) {
        Build build = queue.poll();

        for (int i = 0; i < build.successor.size(); i++) {
            int dest = build.successor.get(i);

            // dest 건물을 짓는 데 걸리는 최소 시간 < dest 건물 짓는데 필요한 시간 + 현재까지 건물 짓는데 걸린 시간
            if (minTime[dest] < buildings[dest].time + build.time) {
                minTime[dest] = buildings[dest].time + build.time;
            }

            // inDegree 를 1씩 감소시킨 각 정점이 inDegree = 0 이라면 큐에 넣는다
            if (--inDegree[dest] == 0) {
                queue.offer(buildings[dest]);
                // dest 건물 짓기까지 걸린 시간 최신화
                buildings[dest].time = minTime[dest];
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        System.out.println(minTime[i]);
    }
}

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static Build[] buildings;
    static int[] inDegree, minTime;
    static Queue<Build> queue;

    static class Build {
        int time;
        ArrayList<Integer> successor;

        public Build(int time, ArrayList<Integer> successor) {
            this.time = time;
            this.successor = successor;
        }

        public void setTime(int time) {
            this.time = time;
        }

        public ArrayList<Integer> getSuccessor() {
            return successor;
        }
    }

    static void getMinTime() {
        while (!queue.isEmpty()) {
            Build build = queue.poll();

            for (int i = 0; i < build.successor.size(); i++) {
                int dest = build.successor.get(i);

                // dest 건물을 짓는 데 걸리는 최소 시간 < dest 건물 짓는데 필요한 시간 + 현재까지 건물 짓는데 걸린 시간
                if (minTime[dest] < buildings[dest].time + build.time) {
                    minTime[dest] = buildings[dest].time + build.time;
                }

                // inDegree 를 1씩 감소시킨 각 정점이 inDegree = 0 이라면 큐에 넣는다
                if (--inDegree[dest] == 0) {
                    queue.offer(buildings[dest]);
                    // dest 건물 짓기까지 걸린 시간 최신화
                    buildings[dest].time = minTime[dest];
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            System.out.println(minTime[i]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        buildings = new Build[N + 1];
        for (int i = 0; i <= N; i++) {
            buildings[i] = new Build(0, new ArrayList<>());
        }

        inDegree = new int[N + 1];
        minTime = new int[N + 1];
        queue = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            buildings[i].setTime(t);
            minTime[i] = t;

            int temp;
            while ((temp = Integer.parseInt(st.nextToken())) != -1) {
                // temp를 선행자로 가지는 건물 번호를 저장한다.
                buildings[temp].getSuccessor().add(i);
                inDegree[i]++;
            }

            if (inDegree[i] == 0)
                queue.offer(buildings[i]);
        }

        getMinTime();
    }
}