[BOJ] BOJ 1516번 '게임 개발' (Java)

[문제]

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

 

[접근방식]

해결 키워드는 '위상 정렬' 과 'DP' 이다.

 

위상 정렬은 우선순위가 정해져 있는 일련의 작업을 차례로 수행해야 할 때 작업 순서를 정해주는 알고리즘이다.

 

현재 건물 건설시 선행 건물의 건설이 필수적인 현재 문제에서 효과적인 알고리즘이다.

 

[위상 정렬 참고자료]

https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

[알고리즘] 위상 정렬 (Topological Sorting)

 

DP 배열 정의 : dp[i] 는 'i' 건물 최소 건설 시간

DP 점화식 개념 : '현재 건물 최소 건설 시간' = '선행 건물 中 가장 오래 걸리는 건설 시간' + '현재 건물 단독 건설 시간'

 

[Java 코드]

/**
 * BOJ_1516 게임 개발
 * https://www.acmicpc.net/problem/1516
 * keyword - '위상 정렬', 'DP'
 */

import java.io.*;
import java.util.*;

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()); //건물의 종류 수
        int[] buildTime = new int[N + 1]; //buildTime[i] = i 건물을 짓는데 걸리는 시간
        int[] inDegree = new int[N + 1]; // 진입차수
        List<Integer>[] graph = new ArrayList[N + 1]; //그래프 - 인접리스트로 표현
        int[] resultTime = new int[N + 1];

        //그래프 초기화
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        //입력 처리
        for (int i = 1; i <= N; i++) {
            StringTokenizer st  = new StringTokenizer(br.readLine());
            buildTime[i] = Integer.parseInt(st.nextToken());

            while (true) {
                int pre = Integer.parseInt(st.nextToken());
                if (pre == -1) break;

                graph[pre].add(i); //선행건물 -> 현재건물
                inDegree[i]++;
            }
        }


        //위상 정렬을 위한 큐
        Queue<Integer> queue = new LinkedList<>();

        //진입 차수가 0인 노드를 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
                resultTime[i] = buildTime[i]; //바로 지을수 있는 건물
            }
        }

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int next : graph[current]) {
                inDegree[next]--; //간선 제거

                //최소 시간 갱신 (선행 건물 중 가장 오래걸리는 건물 + 현재건물 건설시간)
                resultTime[next] = Math.max(resultTime[next], resultTime[current] + buildTime[next]);

                //진입 차수가 0되면 큐에 추가
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }


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

 

[Rewind]

1. 어려웠던 점

- 1. '위상 정렬' 개념 부재, 구현 방식을 알지 못했다.

- '위상 정렬' 의 단어 자체와 " '순서가 정해진 과업'을 차례로 수행해야 할때 그 순서를 결정해 주는 알고리즘 " 이라는 개념을 연관짓지 못했다.

- '위상' 이라는 단어에 익숙하지 않아 뭘 의미하는지 연결짓지 못하였다.

- '위상' Topology : 무언가의 구성이나 연결 방식과 관련된 것 (ex - 네트워크 구성)

 

- 2. DP 점화식을 제대로 이해하지 못했다.

//최소 시간 갱신 (선행 건물 중 가장 오래걸리는 건물 + 현재건물 건설시간)
resultTime[next] = Math.max(resultTime[next], resultTime[current] + buildTime[next]);

단순하게 최소 시간을 구하는 것이 목표인 점화식에 왜 'max' 를 사용하는 것인가에 대한 의문을 꽤 오래 가지고 있었다.

이는 문제 해결 방식을 전혀 이해하지 못한 것이었다.

현재 건물(current) 를 건설하기 위한 선행 건물(next) 중 건설에 가장 오래 걸리는 건물이 건설된 후에야 현재 건물(current)를 건설할 수 있기 때문이다.  

 

2. 알게된 점

- 1. 위상 정렬

- 2. DP를 사용하여 해결하는 새로운 문제

- 3. DP 문제를 무한정으로 해결한다고 해서, 문제 해결 능력이 전혀 늘지 않는다는 사실 

 

3. 개선방안

- 잘 모르겠다.