[백준 1516] 게임 개발

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

1516번: 게임 개발

 

 

먼저 지어져야 하는 건물 -> 순서 존재. => 위상 정렬!!

 

원래 연결 리스트 값을 만들 때 out -> in 형태로 만드는데, 여기에서 주어진 값은 in -> out 형태여서 헷갈렸다..

 

 

 

 

참고

https://steady-coding.tistory.com/86

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

 

 

위상 정렬을 이용한 계산 과정은

degree 값이 0인 '값'(노드)을 큐에 삽입 

- 큐에 삽입된 노드를 꺼낼 때, 꺼낸 노드에 대하여 걸린 시간을 확정짓고,(더이상 고려될 필요가 없으니까.)

  꺼낸 노드를 'in'으로 가지는 다음 노드에 대하여 소요 시간을 업데이트해준다.

 

문제에서 "건물은 동시에 지어질 수 있다" 라고 했으므로,, 

소요 시간을 업데이트 할 때 기존 소요 시간에 어떤 값을 더하는 게 아니라 max 비교만을 통하여 값을 업데이트할 수 있다.

나중에 보면 이거 이해 가려나? 이해 안 가면 위의 링크를 볼 것.

 

 

+우선순위 큐를 이용한 방법도 있음.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        //초기화
        ArrayList<Integer>[] linkedlist = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            linkedlist[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                linkedlist[i + 1].add(Integer.parseInt(st.nextToken()));
            }
        }

        long[] ansArr = topologySort(linkedlist);
        for (int i = 1; i < ansArr.length; i++) {
            System.out.println(ansArr[i]);
        }

    }

    private static long[] topologySort(ArrayList<Integer>[] linkedlist) {
        int length = linkedlist.length-1;
        int[] degree = new int[length + 1];    //degree 수
        ArrayList<Integer>[] outbound = new ArrayList[length + 1];        //이후 값
        for (int i = 1; i <= length; i++) {
            outbound[i] = new ArrayList<>();
            degree[i] = linkedlist[i].size() - 2;
        }

        for (int i = 1; i <= length; i++) {
            int cnt = 1;
            int startNum = linkedlist[i].get(cnt);
            while (startNum != -1) {
                outbound[startNum].add(i);
                startNum = linkedlist[i].get(++cnt);
            }
        }

        long[] costs = new long[length + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= length; i++) {
            if (degree[i] == 0) {
                queue.addLast(i);
                costs[i] = linkedlist[i].get(0);
                degree[i] = -1;
            }
        }
        while (!queue.isEmpty()) {
            int value = queue.removeFirst();
            for (int nextValue : outbound[value]) {
                degree[nextValue]--;
                costs[nextValue] = Math.max(costs[nextValue], costs[value] + linkedlist[nextValue].get(0));
                if (degree[nextValue] == 0) {
                    queue.addLast(nextValue);
                    degree[nextValue] = -1;
                }
            }
        }
        return costs;
    }
}