코딩 테스트 [그래프] - 게임 개발하기

숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준크래프트를 개발하기로 했다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아있다. 게임 플레이어 들어가는 시간은 상황에 따라 다를 수 있기 때문에 모든 건물을 짓는 데 걸리는 최소의 시간을 이용해 근사하기로 했다.

물론 어떤 건물을 짓기 위해서는 다른 건물을 먼저 지어야 할 수도 있으므로 문제가 단순하지는 않다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하므로 배럭을 먼저 지은 후 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한이 많고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정해 보자. N개의 건물을 지을 때 각 건물을 짓기 위해 필요한 최소 시간을 출력하시오.

(시간 제한 2초)

---

입력

1번째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500), 그다음 N개의 줄에는 각 건물을 짓는 데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 가정해 보자. 각 건물을 짓는 데 걸리는 시간은 100,000보다 작거나 같은 자연수다.

출력

N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

예제 입력
5	// 건물 종류 수
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

예제 출력
10
20
14
18
17

---

1단계 - 문제 분석하기

"어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다"의 각 건물을 노드라고 생각하면 그래프 형태에서 노드 순서를 정랼하는 알고리즘인 위상 정렬을 사용하는 문제라는 것을 알 수 있다.

2단계 - 손으로 풀어 보기

1 입력 데이터를 바탕으로 필요한 자료구조를 초기화한다. 인접 리스트로 그래프를 표현 할 때는 (인접 노드, 건물 생산 시간)을 Node로 선언하여 연결한다. 인접 리스트를 보고 진입 차수 배열을 초기화하고, 정답 배열은 모두 0으로 초기화한다.

2 위상 정렬을 실행하면서 각 건물을 짓는 데 걸리는 최대 시간을 업데이트 한다. 업데이트는 다음과 같은 방법으로 수행한다.

Math.max(현재 건물에 저장된 최대 시간, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간)

3 정답 배열에 자기 건물을 짓는 데 걸리는 시간을 더한 후 정답 배열을 차례대로 출력한다.

3단계 - sudo코드 작성하기

N(건물 종류 수), A(데이터 저장 인접 리스트)
indegree(진입 차수 배열) selfBuild(자기 자신을 짓는 데 걸리는 시간 저장 배열)

건물의 개수만큼 인접 리스트 초기화
진입 차수 배열 초기화
자기 자신을 짓는 데 걸리는 시간 저장 배열 초기화

for(건물의 개수)
{
	인접 리스트 데이터 저장
    진입 차수 배열 초기 데이터 저장
    자기 자신 배열 초기화
}

큐 생성
for(건물의 개수)
{
	진입 차수 배열의 값이 0인 노드를 큐에 삽입
}
while(큐가 빌 때까지)
{
	현재 노드 = 큐에서 데이터 poll
    for(현재 노드에서 갈 수 있는 노드의 개수)
    {
    	타깃 노드 진입 차수 배열--
        결과 노드 업데이트 = Math.max(현재 저장된 값, 현재 출발 노드 + 비용)
        if(타깃 노드의 진입 차수가 0이면)
        {
        	우선순위 큐에 타깃 노드 추가
        }
    }
}
결과 출력

4단계 - 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q54 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer>[] A = new ArrayList[N + 1];
        for(int i = 1; i < N+1; i++){
            A[i] = new ArrayList<Integer>();
        }

        int[] indegree = new int[N+1];
        int[] selfBuild = new int[N+1];
        int[] result = new int[N+1];

        for(int i = 1; i < N+1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            selfBuild[i] = Integer.parseInt(st.nextToken());
            while (true){
                int tmp = Integer.parseInt(st.nextToken());
                if(tmp == -1){
                    break;
                }
                A[tmp].add(i);
                indegree[i]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i < N+1; i++){
            if(indegree[i] == 0)
                queue.add(i);
        }
        while (!queue.isEmpty()){
            int now = queue.poll();
            for(int i = 0; i < A[now].size(); i++){
                indegree[A[now].get(i)]--;
                result[A[now].get(i)] = Math.max(result[A[now].get(i)], result[now] + selfBuild[now]);

                if(indegree[A[now].get(i)] == 0){
                    queue.add(A[now].get(i));
                }
            }
        }

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

---

• Do it! 알고리즘 코딩테스트 자바 편