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

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

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

1. 문제 접근

N개의 건물이 존재하고 각 건물을 건설하는데 선행 건물들이 존재 할 때, 각 건물들의 건설에 필요한 최소 시간을 구하면 되는 문제다.

 

각 건물들을 건설하는데 있어 "선행 건물"이 존재한다는 것으로부터 위상정렬(topology sort)를 통해 풀 수 있다는 것을 알 수 있다. 

 

문제를 조금 작은 문제로 집중하여 살펴 보자.

 

A 건물을 건설하는데 있어 B, C, D 건물이 필요할 때 A건물을 건설할 때 소요 시간은 B, C, D를 건설하는 데 걸리는 시간의 최대값 + A건물을 건설하는 시간이다.

 

여러 건물들이 동시에 지어질 수 있으므로 A건물의 건설에 집중하면 중요한 것은 B, C, D 중 가장 늦게 건설이 끝나는 건물에 영향을 받는다는 것이다.

 

위상 정렬을 사용하게 되면, A는 B, C, D 이후에 탐색이 진행될 수 밖에 없다. (B, C, D를 탐색해야만 A의 진입 차수가 0에 도달할 수 있다.)

 

따라서 B, C, D를 조회하며 지속적으로 A의 건설시간을 갱신해주어야 한다.

 

아래는 위의 예시를 일반화 한 코드다

 

// adNode(이후에 지을 건물)의 최소 시간을 갱신
totalTime[adNode] = Math.max(totalTime[currNode] + reqTime[adNode], totalTime[adNode]);

 

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * [BOJ] - 게임 개발 / 1516번 
 * @author JinHxxxxKim
 * 
 * 1. 건물에 대한 정보를 노드로, 선행 건물에 대한 정보를 엣지로 인식
 * 2. A건물이 B건물의 선행건물일 경우, A -> B 의 형태로 그래프 형성
 * 3. 위상정렬을 수행
 * 		3-1. 각 노드(건물)을 방문할 때마다 인접 노드의 소요시간을 갱신.
 */
public class Sol_1516 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static int N; // 건물 개수
	private static List<Integer>[] adList; // 인접리스트
	private static int[] inDgree; // 진입차수
	private static int[] reqTime; // 건물을 짓는데 걸리는 시간
	private static int[] totalTime; // 선행 건물을 짓고 최종적으로 걸리는 시간

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine().trim());
		adList = new List[N + 1];
		reqTime = new int[N + 1];
		totalTime = new int[N + 1];
		inDgree = new int[N + 1];
		for (int idx = 1; idx < N + 1; ++idx) {
			adList[idx] = new ArrayList<Integer>();
		}
		for (int currNode = 1; currNode < N + 1; ++currNode) {
			st = new StringTokenizer(br.readLine().trim());
			reqTime[currNode] = Integer.parseInt(st.nextToken());
			int reqNode = Integer.parseInt(st.nextToken());
			while (reqNode != -1) {
				// currNode를 짓는데 reqNode가 필요
				// reqNode -> currNode
				adList[reqNode].add(currNode);
				reqNode = Integer.parseInt(st.nextToken());
				// currNode의 진입차수 +1
				inDgree[currNode]++;
			}
		}

		// 위상정렬 시작
		Queue<Integer> q = new ArrayDeque<>();
		// 1. 진입차수가 0인 노드 삽입
		for (int idx = 1; idx < N + 1; ++idx) {
			if (inDgree[idx] == 0) {
				q.offer(idx);
				totalTime[idx] = reqTime[idx];
			}
		}

		// 2. Queue에서 꺼낸 노드의 인접노드 확인
		while (!q.isEmpty()) {
			int currNode = q.poll();
			for (int adNode : adList[currNode]) {
				--inDgree[adNode];
				// 진입차수가 0이되었다면 queue에 삽입
				if (inDgree[adNode] == 0) {
					q.offer(adNode);
				}
				// adNode(이후에 지을 건물)의 최소 시간을 갱신
				totalTime[adNode] = Math.max(totalTime[currNode] + reqTime[adNode], totalTime[adNode]);
			}
		}
		for (int idx = 1; idx < N + 1; ++idx) {
			sb.append(totalTime[idx]).append("\n");
		}
		System.out.println(sb);
	}
}

---

3. 디버깅

 

처음에 문제를 풀 때, DP적인 요소를 고려하지 않고 구현했다.

 

if (inDgree[adNode] == 0) {
    q.offer(adNode);
    totalTime[adNode] = reqTime[adNode] + totalTime[currNode];
}

 

위와 같이 구현하게 되면 예제와 같은 경우가 아닌, 서로 관련이 없는 건물들이 동시에 선행건물로 요구될 때 올바른 결과가 나오지 않는다.

 

특정 알고리즘이 떠올랐다고 너무 해당 알고리즘에만 매몰되지 않고 다양한 알고리즘을 동시에 적용해봐야겠다.

 

추가적으로 1년전에 작성한 코드를 보는데 위상정렬을 쓰지 않고 풀었던데 주석이 없어 정확한 이해가 어려워 주석에 조금 더 신경써야겠다.

 

---

4. 결과