[백준 1516] 게임 개발 (JAVA)

백준(BOJ) 1516 게임 개발

 

난이도
221220 기준 골드 3

사용 알고리즘
위상정렬

문제 링크
https://www.acmicpc.net/problem/1516

1516번: 게임 개발

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

 

입력

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

 

출력

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

 

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 문제에서 "어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문" 이 부분을 보면 위상정렬을 써야하지 않을까 하는 감이 오네요 N도 500 이하이고 딱히 시간초과가 날 곳은 보이지 않습니다. 위상 정렬을 사용해서 문제를 풀어보겠습니다.

 

 

3. 풀이 구상

 

 위상정렬 알고리즘을 쓰는 문제는 위상정렬 알고리즘을 이해하고 코드를 짜는 법을 알면 쉽게 풀 수 있습니다. 저도 오랜만에 풀어보는데요 한 번 기억을 더듬어 풀어보겠습니다.

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

// 백준 1516번 게임 개발
public class Main {
	
	static int N;
	static int[] ownBuildTimes;
	static int[] minBuildTimes;
	static List<Integer>[] frontList;
	static List<Integer>[] backList;
	static int[] backCnt;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	N = Integer.parseInt(br.readLine());
    	
    	ownBuildTimes = new int [N+1];
    	minBuildTimes = new int [N+1];
    	
    	backList = new List[N+1];
    	frontList = new List[N+1];
    	backCnt = new int[N+1];
    	
    	for(int i = 1; i <= N; i++) {
    		frontList[i] = new ArrayList<>();
    		backList[i] = new ArrayList<>();
    	}
    	
    	for(int i = 1; i <= N; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		
    		int time = Integer.parseInt(st.nextToken());
    		ownBuildTimes[i] = time;
    		
    		int bef = Integer.parseInt(st.nextToken());
    		while(bef!=-1) {
    			backList[i].add(bef);
    			backCnt[i]++;
    			frontList[bef].add(i);
    			bef = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	
    	topologySort();
    	
    	for(int i = 1; i <= N; i++) {
    		bw.write(minBuildTimes[i]+"\n");
    	}
    	bw.flush();
        bw.close();
        br.close();
    }
    
    static void topologySort() {
    	
    	Queue<Integer> q = new LinkedList<>();
    	for(int i = 1; i <= N; i++) {
    		if(backCnt[i]==0) {
    			q.offer(i);
    		}
    	}
    	
    	
    	while(q.size()>0) {
    		int cur = q.poll();
    		
    		// befMax 이전에 짓는 건물들중 가장 오래걸리는 시간
    		int befMax = 0;
    		for(int i = 0, size = backList[cur].size(); i < size; i++) {
    			befMax = Math.max(befMax, minBuildTimes[backList[cur].get(i)]);
    		}
    		minBuildTimes[cur] = befMax + ownBuildTimes[cur];
    		
    		
    		for(int i = 0, size = frontList[cur].size(); i < size; i++) {
    			if(--backCnt[frontList[cur].get(i)]==0) {
    				q.offer(frontList[cur].get(i));
    			}
    		}
    	}
    	
    	
    }
    

}

 

 

2. 오답 노트 & 주의할 점

 

 2-1 오답노트 - 초기화에서 실수

 처음 코드를 제출 했을 때 NullPointerException이 떠서 어디서 떴을까 찾아봤는데

frontList[i] = new ArrayList<>();
backList[i] = new ArrayList<>();

 이 두 리스트배열의 초기화를 입력값을 받을 때 해주는 바람에 while(bef!=-1)안에 frontList[bef].add(i) 부분에서 아직 bef인덱스의 frontList에 null 값이 있는 경우가 있어 틀렸습니다. 위에서 먼저 for문 돌려서 초기화 하면서 간단히 해결했습니다.

 

 2-2 주의할 점

 위상정렬 문제는 오랜만에 풀어봤습니다. 예전에 풀었던 문제들은 현재 노드의 후행 노드들만 따로 저장해줬던걸로 기억했는데 이 문제는 선행 노드들도 따로 저장을 해줘야 현재 노드의 최소 완성 시간을 구할 수 있기에 두 가지 모두 저장을 해줬습니다. 다만 아쉬운건 저는 frontList, backList로 따로 따로 저장을 해줬는데 하나로 합칠 수 도 있지 않을까 하는 생각을 합니다.

 

풀이 후기

 오랜만에 위상정렬 문제를 푸니까 이렇게 하는거 맞나 하면서 코드를 짜게 됩니다. 크루스칼, 프림, 다익스트라도 조금씩 가물가물해지는데 하나씩 풀어봐야겠습니다.