문제 설명
위상 정렬 문제로 진입차수가 없는(선행 작업이 존재하지 않은) 노드들을 먼저 실행시키고 작업이 완료되면 하위 노드의 차수를 감소시켜 진입차수가 0이 되는 노드의 작업을 시작하는 방식으로 접근했다. 시간 제한이 2초로 나름? 여유가 있어 1시간 단위로 반복문을 실행해 작업중인 노드의 time 값을 감소시켜 0이 되면 위 작업을 실행하도록 코드를 작성했다.
정답 코드(라고 생각했던 것)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
int[] degree = new int[n + 1];
int[] time = new int[n + 1];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
int cnt = Integer.parseInt(st.nextToken());
degree[i] = cnt;
for (int j = 0; j < cnt; j++) {
int parent = Integer.parseInt(st.nextToken());
graph.get(parent).add(i);
}
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
if (degree[i] == 0) {
q.add(i);
}
}
int cnt = 0;
while (!q.isEmpty()) {
for (int i = 0; i < q.size(); i++) {
int t = q.poll();
time[t]--;
if (time[t] == 0) {
List<Integer> nodes = graph.get(t);
for(Integer node: nodes){
degree[node]--;
if(degree[node] == 0){
q.add(node);
}
}
} else {
q.add(t);
}
}
cnt++;
}
System.out.println(cnt);
}
}주요 알고리즘
int cnt = 0;
while (!q.isEmpty()) {
for (int i = 0; i < q.size(); i++) {
int t = q.poll();
time[t]--;
if (time[t] == 0) {
List<Integer> nodes = graph.get(t);
for(Integer node: nodes){
degree[node]--;
if(degree[node] == 0){
q.add(node);
}
}
} else {
q.add(t);
}
}
cnt++;
} queue에 담겨있는(진행중인 작업)을 가져와 time값을 감소시키고 time이 0이 아닐 때는 다시 queue에 넣어 작업을 계속 진행하도록 했다. 최저 시간을 출력하는 문제이지만 어짜피 하위 노드의 작업은 모든 상위 노드가 끝났을 때 진행되기 때문에 별다른 비교연산없이 이상적으로 동시에 작업이 진행된다고 생각했다...결과를 확인하기 전까지
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
int[] degree = new int[n + 1];
int[] time = new int[n + 1];
int[] cTime = new int[n + 1];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
int cnt = Integer.parseInt(st.nextToken());
degree[i] = cnt;
for (int j = 0; j < cnt; j++) {
int parent = Integer.parseInt(st.nextToken());
graph.get(parent).add(i);
}
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
if (degree[i] == 0) {
q.add(i);
cTime[i] = time[i];
}
}
while (!q.isEmpty()) {
int current = q.poll();
for (Integer next : graph.get(current)) {
degree[next]--;
cTime[next] = Math.max(cTime[next], cTime[current] + time[next]);
if(degree[next] == 0){
q.add(next);
}
}
}
int result = 0;
for (int i = 1; i <= n; i++) {
result = Math.max(result, cTime[i]);
}
System.out.println(result);
}
} for (int i = 1; i <= n; i++) {
if (degree[i] == 0) {
q.add(i);
cTime[i] = time[i];
}
}
while (!q.isEmpty()) {
int current = q.poll();
for (Integer next : graph.get(current)) {
degree[next]--;
cTime[next] = Math.max(cTime[next], cTime[current] + time[next]);
if(degree[next] == 0){
q.add(next);
}
}
} cTime이라는 완료시간을 저장하는 배열을 선언하고 정점인 노드 즉, 가장 먼저 작업을 시작하는 노드의 값은 해당 작업이 걸리는 시간을 할당한다. 이후 다음과 같은 연산을 통해 해당 노드가 작업이 완료된 시간을 정한다.
다음과 같은 상황이 있다고 가정하자. (실제로 cTime[3]은 값이 없지만 편의상 해당 작업의 시간이라고 생각한다.)
1,2 작업이 동시에 시작되며 15시간이 걸리는 1작업이 먼저 끝나고 연산을 통해 cTime[3]은 20이 된다.
이후 2작업이 5시간 뒤에 끝나게 되고 이전의 값인 20과 새롭게 계산한 25중에서 큰 값인 25로 설정해서 상위 작업이 전부 끝나고 완료된 시간을 기록하게 된다.
정리
사실 아직 첫번째 만든 코드가 틀린 이유는 잘 모르겠다.(물론 깔끔한 코드라고 생각은 안함 ㅎ) 상위 작업이 끝난 후에 작업이 끝나도록 코드를 작성했기 때문에 예제와 질문 게시판에 있는 반례 몇개를 해봤지만 제대로 정답이 출력되었기 때문이다. 시간초과라고 뜨면 납득이 되겠지만 채점이 틀렸다고 한건 분명 반례가 있다는건데... (있으면 댓글 부탁드림다.)
어쨌든 위상정렬에 대해서 좀 더 확실한 이해가 되었던 문제였다고 생각한다. 🙃
