[1516] 게임 개발

✔ 게임 개발

[백준 1516]

문제 분석하기

어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있으므로

각 건물을 노드라고 생각하면 그래프 형태에서 노드 순서를 정렬하는 알고리즘인 위상 정렬을 사용하는 것으로 문제에 접근

손으로 풀어보기

1. 입력 데이터를 바탕으로 필요한 자료구조인 건물 생산 시간, 진입 차수 리스트, 정답 리스트를 초기화
   • 인접 리스트로 그래프를 표현하고 건물의 생성 시간을 따로 저장
2. 위상 정렬을 실행하면서 각 건물을 짓는데 걸리는 최대 시간을 업데이트
   • Math.max(현재 건물에 저장된 최대 시간, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간)
3. 정답 배열에 자기 건물을 짓는데 걸리는 시간을 더한 후 정답 배열을 차례대로 출력

슈도코드 작성하기

N(건물 종류 수) A(데이터 저장 인접 리스트)
건물의 개수만큼 인접 리스트 초기화하기
진입 차수 배열 초기화하기
자기 자신을 짓는데 걸리는 시간 저장 배열 초기화하기
for(건물의 개수) {
    인접 리스트 데이터 저장하기
    진입 차수 배열 초기 데이터 저장하기
    자기 자신 배열 초기화하기
]

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

코드 구현하기

/**
 * 1516) 게임_개발
 */
public class D054_1516 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(건물 종류 수)
        int N = Integer.parseInt(br.readLine());
        // A(데이터 저장 인접 리스트)
        ArrayList<ArrayList<Integer>> A = new ArrayList<>();
        // 건물의 개수만큼 인접 리스트 초기화하기
        for (int i = 0; i <= N; i++) {
            A.add(new ArrayList<>());
        }
        // 진입 차수 배열 초기화하기
        int[] indegree = new int[N + 1];
        // 자기 자신을 짓는데 걸리는 시간 저장 배열 초기화하기
        int[] selfBuild = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 건물을 짓는데 걸리는 시간 저장하기
            selfBuild[i] = Integer.parseInt(st.nextToken());
            // 인접 리스트 데이터 저장하기
            while (true) {
                int preTemp = Integer.parseInt(st.nextToken());
                if (preTemp == -1)
                    break;
                A.get(preTemp).add(i);
                // 진입 차수 배열 초기 데이터 저장하기
                indegree[i]++;
            }
        }
        // 큐 생성하기
        Queue<Integer> queue = new LinkedList<>();
        // 진입 차수 배열의 값이 0인 건물을 큐에 삽입하기
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        int[] result = new int[N + 1];
        while (!queue.isEmpty()) {
            // 현재 노드 = 큐에서 데이터 poll
            int now = queue.poll();
            // 현재 노드에서 갈 수 있는 노드
            for (int next : A.get(now)) {
                // 타깃 노드 진입 차수 배열 --
                indegree[next]--;
                // 결과 노드 업데이트 = Math.max(현재 저장된 값, 현재 출발 노드 + 비용)
                result[next] = Math.max(result[next], result[now] + selfBuild[now]);
                // 타깃 노드의 진입 차수가 0이면
                if (indegree[next] == 0) {
                    // 큐에 타깃 노드 추가하기
                    queue.offer(next);
                }
            }
        }
        // 위상 정렬 결과 출력하기
        for (int i = 1; i <= N; i++) {
            // 자기 건물을 짓는데 걸리는 시간을 더함
            System.out.println(result[i] + selfBuild[i]);
        }
    }
}