[BOJ] 백준 1516 게임개발

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

 Input 

5

10 -1

10 1 -1

4 1 -1

4 3 1 -1

3 3 -1

 

 Output 

10
20
14
18
17

위상정렬 (Topological sort)  

위상정렬 (Topological sort)

▶ 진입차수를 이용한 위상 정렬 이용.

1. 자기 자신으로 들어오는 간선이 없는 정점을 모두 찾아 queue 저장

2. 위에서 찾은 정점(들)과 그 정점으로 부터 나오는 간선을 그래프에서 삭제한다.

진입차수indegree = [0 1 1 2 1]

각 건물의 의존관계를 적용해서 건물 짓는 시간은 다음과 같습니다.

①; 10초

②; ①번 건물 선행 → 10 + 10 = 20

③; ①번 건물 선행 → 10 + 4 = 14

④; ①, ③번 건물 선행  →  10 + 4 + 4 = 18

⑤; ①, ③번 건물 선행  → 10 + 4  + 3 = 17

 

※ 사이클을 형성하는 경우 간선을 없애는 과정에서 

어느 순간 indegree = 0이 되는 정점이 존재하지 않아 

모든 간선을 완전히 없애지 못하게 된다.

 

시뮬레이션

▶ 진입차수가 0이 정점의 건물 짓는 시간을 answer 할당.

indegree = [0 1 1 2 1]

answer = [10, 0, 0, 0, 0]

 

 

▶ 정점 ①과 연결된 정점 ②, ③, ④ 처리.

indegree = [0 0 0 1 1]

answer = [10, Max(0, 10 + 10), Max(0, 10 + 4), Max(0, 10 + 4), 0] 

                 [10, 20, 14, 14, 0]

 

 

▶ 진입차수 = 0인 정점 ②, ③과 연결된 정점 처리

     - 정점 ②과 연결된 정점 없음

     - 정점 ③과 연결된 정점 ④, ⑤ 처리.

        * 인덱스를 편의상 『1』부터 시작한다고 가정

        answer[4] = Max(answer[4], answer[3] + buildTime[4])

                          = Max(14, 14+4), 

        answer[5] = Max(answer[5], answer[3] + buildTime[5])

                           = Max(0, 14+3)

 

indegree = [0 0 0 0 0]

answer =  [10, 20, 14, 18, 17]

 

다른 case

indegree = [0 0 2]

answer = [10, 20, 0]

 

 

indegree = [0 0 1]

answer = [10, 20, Max(0, 10+5)]

             = [10, 20, 15]

 

 

indegree = [0 0 0]

answer = [10, 20, Max(15, 20+5)]

             = [10, 20, 25]

 

▶ 정점에 이르기까지 가장 오래 걸린 비용을 answer[]에 저장하는 방식

---

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    static ArrayList<ArrayList<Integer>> adList;
    static int N;
    static int[] indegree, buildTime, answer;
    static Queue<Integer> queue;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 정점의 개수
        N = Integer.parseInt(sc.next());
        indegree = new int[N+1];
        buildTime = new int[N+1];
        
        // 인접 리스트로 구현
        adList = new ArrayList<>();
        adList.add(new ArrayList<>());
                
        // 1~N까지의 각 정점을 리스트에 삽입
        for(int i=1; i<=N; i++) {
            adList.add(new ArrayList<>());
        }
        
        for(int i=1; i<=N; i++) {
            buildTime[i] = Integer.parseInt(sc.next());
            
            // 해당 건물을 짓기전에 미리 지어져야 하는 건물이 있다면
            int vertex = Integer.parseInt(sc.next());
            while(vertex != -1) {
                adList.get(vertex).add(i);
                indegree[i]++;
                vertex= Integer.parseInt(sc.next());
            }
            
        }
        answer = new int[N+1];
        queue = new LinkedList<>();
        // 위상정렬
        topological_sort();
        
        // 정답 출력
        for(int i=1; i<=N; i++) {
            System.out.println(answer[i]);
        }
        
    }

    private static void topological_sort() {
        for(int i=1; i<=N; i++) {
            if(indegree[i] == 0) {
                queue.add(i);
                answer[i] = buildTime[i];
            }
        }
        
        for(int i=1; i<=N; i++) {
            int pre = queue.poll();
            ArrayList<Integer> curNodeList = adList.get(pre);
            // 연결된 지점을 찾는다.
            while(!curNodeList.isEmpty()) {
                int current = curNodeList.remove(0);
                answer[current] = Math.max(answer[pre] + buildTime[current], answer[current]);
                
                // 진입 차수 갱신
                indegree[current]--;
                if(indegree[current] == 0) {
                    queue.add(current);
                }
            }
        }
    }
}