문제
https://www.acmicpc.net/problem/1005
풀이
건설 순서 규칙이 있는 방향 그래프(사이클X)이므로 위상 정렬을 사용해서 문제를 풀 수 있다.
위상정렬 문제를 푸는 것처럼 문제를 풀면 되지만, 목표한 건물을 짓는데 걸리는 시간을 구하기 위해서는 각 건물을 짓는데 소요되는 시간을 기록해야 한다.
문제에서 주어진 예시를 보면, 4번 건물을 짓기 위해서는 2번, 3번 건물이 지어져있어야 하므로 두 건물을 짓는 시간 중 최대 시간만큼 기다려야 한다. 따라서 4번 건물을 짓기 위해서는 10초 + Max(1초, 100초) + 10초 = 120초가 소요된다.
이러한 로직을 위상정렬을 수행할 때 추가해서 문제를 풀면 된다. 자세한 내용은 코드를 참고하면 된다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ_1005 {
static int N, K;
static int[] inDegree, times, delay;
static ArrayList<Integer>[] graph;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
for (int t = 0; t < T; t++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
delay = new int[N + 1];
times = new int[N + 1];
inDegree = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
times[i] = Integer.parseInt(st.nextToken());
}
graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
// 건설 순서: a -> b
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
inDegree[b]++; // 진입 차수 증가
graph[a].add(b); // 건설 순서 저장
}
int target = Integer.parseInt(br.readLine());
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 1; i <= N; i++) {
// 진입 차수가 0인 건물 큐에 넣기
if (inDegree[i] == 0) {
queue.offer(i);
delay[i] = times[i];
}
}
while (!queue.isEmpty()) {
int now = queue.poll();
if (now == target)
break;
for (int next : graph[now]) {
// next 건물을 짓기 전까지 소요되는 최대 시간 구하기
// 선수 건물들이 다 지어질 때까지 기다려야 하므로 최대 시간을 구해야 함
delay[next] = Math.max(delay[next], delay[now] + times[next]);
// 진입차수가 0이 되면 큐에 넣기
if (--inDegree[next] == 0) {
queue.offer(next);
}
}
}
sb.append(delay[target]).append("\n");
}
System.out.println(sb);
}
}
후기
처음에는 단순하게 위상정렬로만 문제를 풀었는데 그러면 아주 큰 예외가 있다는 것을 틀리고 난 뒤에 알았다.. 그래서 시간을 기록하는 배열을 추가해서 문제를 풀었다.
그리고 나는 해당 건물을 짓는데 소요되는 시간을 역방향 그래프를 이용해서 구했는데 다른 분의 풀이를 보니 연결된 건물을 확인할 때 구할 수 있다는 것을 알게 되었다..! 이래서 다른 코드를 많이 봐야하는 것 같다. 암튼 많이 헤맸으니 나중에 또 풀어보자..!
