[백준 2056] 작업 - JAVA

문제 링크

문제 정의

• $N$개의 작업이 주어지며 각 작업의 번호는 $1~N$
• 해당 작업 소요 시간과 선행 관계에 있는 작업 수가 주어짐
• 이 때 모든 작업을 완료하기 위한 최소 시간을 출력

접근 방법

해당 문제는 위상 정렬로 접근했습니다.
가장 기본적인 구조의 위상 정렬로 문제를 해결할 수 있지만
몇 가지 주의 사항이 있었습니다.

주어지는 값이 진입 노드인지 진출 노드인지 확인하기

현재 작업 $v$의 소요 시간과 이후에 노드들이 주어지는데
"선행 관계에 있는 작업들의 번호가 주어진다"이라고 적혀있었습니다.

주어지는건 현재 작업을 수행하기 위해 선행해야할 작업들이고
그렇기 때문에 나를 필요로 하는 값이 오는 것이기 때문에
진입차수인 in[v]++을 증가시켜야 합니다.

만약 주어지는 노드가 현재 노드를 수행해야만 할 수 있는 값으로 주어진다면
반대로 in[nv]++를 해줘야 하는 점에 주의해서 문제를 풀어야 합니다.

이 점에 주의해서 문제를 푼다면 위상 정렬 문제도 막힘없이 풀 수 있을 것입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;


class Node {
	int v;
	Node node;

	public Node (int v, Node node) {
		this.v = v;
		this.node = node;
	}
}

public class Main {
	static StringTokenizer st;
	static Node[] graph;
	static int[] cost;
	static int[] in;
	static int N;


	public static void main(String[] args) throws IOException {
		init();
		System.out.println(topologicalSort());
	}

	private static int topologicalSort() {
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int[] total = new int[N+1];

		for (int v = 1; v <= N; v++) {
			total[v] = cost[v];
			if (in[v] == 0) {
				q.offer(v);
			}
		}

		int result = 0;
		while (!q.isEmpty()) {
			int v = q.poll();

			result = Math.max(result, total[v]);

			for (Node node = graph[v]; node != null; node = node.node) {
				int nv = node.v;

				total[nv] = Math.max(total[nv], total[v] + cost[nv]);

				if (--in[nv] == 0) q.offer(nv);
			}
		}
		return result;
	}



	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		in = new int[N+1];
		cost = new int[N+1];
		graph = new Node[N+1];

		for (int v = 1; v <= N; v++) {
			st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			int count = Integer.parseInt(st.nextToken());

			cost[v] = time;

			while (count-- > 0) {
				int nv = Integer.parseInt(st.nextToken());
				graph[nv] = new Node(v, graph[nv]);
				in[v]++;
			}
		}
	}
}