백준 1005번 ACM Craft :: 마이구미

이번 글은 백준 알고리즘 문제 1005번 "ACM Craft" 를 다뤄본다.

문제 번호를 보다시피, 오래된 문제로 제출량이 만건이 넘은 문제이다.

정답률이 17%밖에 안되지만, 어려운 문제가 아닌, 쉬운 문제로 속한다.

1년 전 풀었지만, 재채점으로 인해 런타임에러가 떴기에, 복습 겸 다시 풀어보았다.

문제 풀이의 접근은 위상 정렬을 활용한다.

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

문제를 확실히 읽고 이해해야한다.

4번 건물을 짓기 위해 2번 경로와 3번 경로를 이용할 수 있다.

문제는 두 경로 중 어떤 것을 택하는 문제가 아니라는 것을 확실히 이해해야한다.

단순히 위상 정렬을 활용하면 된다.

위상 정렬은 다양한 구현 방법이 있지만, 본인은 indegree 를 이용했다.

indegree는 한 정점에서 자신에게 들어오는 방향인 간선의 갯수이다.

주의할 점은 언급했듯이, 확실히 문제를 이해하는 것이다.

정점에 대해 최대 시간이 건물의 최소 시간이 된다.

동시에 건물이 지을 수 있어도, 동시에 짓기 시작한 건물이 모두 완성되어야 다음 건물을 지을 수 있기 때문이다.

while (!q.isEmpty()) {
    int v = q.poll();
    for (int i = 1; i < len; i++) {
        if (adj[v][i]) {
            result[i] = Math.max(result[i], result[v] + time[i]);

            if (--indegree[i] == 0) {
                q.add(i);
            }
        }
    }
}

위상 정렬에 대해 잘 정리된 아래 링크를 참고하길 바란다.

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 1005번 "ACM Craft" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/sort/1005.java

위상 정렬 참고 링크

http://jason9319.tistory.com/93

public static int[] topologicalSort(boolean[][] adj, int[] indegree, int[] time) {
    Queue<Integer> q = new LinkedList<>();
    int len = indegree.length;
    int[] result = new int[len];
    for (int i = 1; i < len; i++) {
        if (indegree[i] == 0) {
            result[i] = time[i];
            q.add(i);
            break;
        }
    }
    while (!q.isEmpty()) {
        int v = q.poll();
        for (int i = 1; i < len; i++) {
            if (adj[v][i]) {
                result[i] = Math.max(result[i], result[v] + time[i]);
                if (--indegree[i] == 0) {
                    q.add(i);
                }
            }
        }
    }
    return result;
}