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

 

---

 

• 생각

1. 배열을 만들어서 지어도 되는 건물 index를 먼저 채워 넣으며 다른 건물을 더 해준다. 이걸 어떻게 구현해야 될 지 찾아보니 이런 상황에서 풀 때 쓰면 좋은 알고리즘을 찾았다. 위상 정렬이라는 알고리즘이다.

 

 

위상 정렬 (velog.io/@max9106/Algorithm-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-Sort - 직접 정리해서 링크 바꿔 놓자!) 

- 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

- DAG(Directed Acyclic Graph: 사이클이 존재하지 않는 방향 그래프)에만 적용할 수 있다.

 

 

 

• 코드

정답 코드 : 위상 정렬을 큐를 사용하여 구현한 코드이다. 위상 정렬을 처음 접해 보았는데 코드가 깔끔하다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
        int N = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<Integer>> preBuildingNumber = new ArrayList<>();
 
        for (int i = 0; i <= N; i++) {
            preBuildingNumber.add(new ArrayList<>());
        }
 
        int[] indegree = new int[N + 1]; // 특정 건물을 짓기 전에 먼저 지어야 할 건물의 개수
        int[] times = new int[N + 1]; // 특정 건물을 짓는 데 걸리는 시간
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
 
            times[i] = Integer.parseInt(st.nextToken());	// 해당 건물을 짓기 위한 시간
            while (true) {
                int preBuildingNumberTemp = Integer.parseInt(st.nextToken());
 
                if (preBuildingNumberTemp == -1)
                    break;
 
                preBuildingNumber.get(preBuildingNumberTemp).add(i);
 
                indegree[i]++;		// 해당 건물을 짓기 전 지어야 할 건물의 수를 더해준다.
            }
        }
 
        String timeForBuilding = topologicalSort(preBuildingNumber, indegree, times, N);
 
        System.out.print(timeForBuilding);

    }
    
    // 위상 정렬
    public static String topologicalSort(ArrayList<ArrayList<Integer>> a, int[] indegree, int[] times, int N) {
        Queue<Integer> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        
        // 먼저 지어야할 건물이 없는 건물을 큐에 집어 넣음. 해당 큐에 있는 건물을 먼저 짓는다.
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 특정 건물을 짓기 전까지 걸린 시간 누적
        int[] result = new int[N + 1];
 
        while (!queue.isEmpty()) {
            int now = queue.poll();
 
            for (int next : a.get(now)) {
                indegree[next]--;
                
                // indegree를 줄여나가는 과정
                // result[next] = max(result[next], result[now] + times[now])
                // 위의 수식을 활용하여 result의 값을 초기화하는 것이 핵심
                result[next] = Math.max(result[next], result[now] + times[now]);
 
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        // 특정 건물을 짓기 전 먼저 지어야할 건물의 시간 + 특정 건물을 짓는 시간
        for (int i = 1; i <= N; i++) {
            sb.append((result[i] + times[i]) + "\n");
        }
 
        return sb.toString();
    }
}