백준 1516 게임 개발 python, java

위상정렬 알괴즘을 알고 있다면 어렵지 않게 풀 수 있는 문제였다.

📜 문제 바로 가기 : 게임 개발

제출코드

파이썬

import sys
input = sys.stdin.readline

N = int(input())
buildings = [[] for _ in range(N+1)] # i를 지어야 지을 수 있는 빌딩들
enter_cnt = [0] * (N+1)
time = [0] * (N+1)
for i in range(1, N+1):
    a = list(map(int, input().split()))
    time[i] = a[0]
    enter_cnt[i] = len(a) -2
    for j in range(1, len(a)-1):
        buildings[a[j]].append(i)

ans = [0] * (N+1)
while 1:
    # 1. 진입차수 0인 얘들 찾기
    stack = []
    for i in range(N+1):
        if enter_cnt[i] == 0:
            stack.append(i)
            enter_cnt[i] = -1
    
    if len(stack) == 0:
        break
    
    # 건물 짓고 시간체크
    for b in stack:
        ans[b] += time[b]
        for c in buildings[b]:
            enter_cnt[c] -= 1
            ans[c] = max(ans[c], ans[b])

for i in range(1, N+1):
    print(ans[i])

자바

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

public class Main {

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

        int N = Integer.parseInt(st.nextToken());
        ArrayList<Integer>[] buildings = new ArrayList[N+1];
        for (int i = 1; i < N+1; i++) {
            buildings[i] = new ArrayList<>();
        }
        int[] enter_cnt = new int[N+1];
        int[] time = new int[N+1];

        for (int i = 1; i < N+1; i++) {
            st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            int cnt = 0;
            while (1 < 10) {
                int j = Integer.parseInt(st.nextToken());
                if (j == -1) {
                    break;
                }
                cnt += 1;
                buildings[j].add(i);
            }
            enter_cnt[i] = cnt;
        }

        int[] ans = new int[N+1];
        while (1 < 10) {
            ArrayList<Integer> stack = new ArrayList<>();
            for (int i = 1; i < N+1; i++) {
                if (enter_cnt[i] == 0) {
                    stack.add(i);
                    enter_cnt[i] = -1;
                }
            }

            if (stack.size() == 0) {
                break;
            }

            for (int b : stack) {
                ans[b] += time[b];
                for (int c : buildings[b]) {
                    enter_cnt[c] -= 1;
                    ans[c] = Math.max(ans[c], ans[b]);
                }
            }
        }

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

---

접근방법

i번째 빌딩의 진입차수를 알 수 있는 buildings 와
진입차수가 0인 빌딩을 좀 더 빠르게 찾기 위한 enter_cnt 배열을 만들었다.

최종적으로 지어지는 건물 시간에서 조금 생각이 필요했는데, 진입차수가 0인 건물들은 바로 시간을 더해주면 되고 i 번째 건물을 지을때 i 건물을 진입차수로 갖는 j 건물의 완공 시간은 가장 늦게 지어지는 건물에 맞춰져야 함으로 ans[j] = max(ans[j], ans[i]) 로 나타낼수 있겠다.