[BOJ] 백준 2056번 : 작업 (JAVA)

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

 

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

 

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

 

입력

첫째 줄에 N이 주어진다.

 

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

 

 

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

 

 

풀이

위상정렬 또는 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

이 글에서는 두 가지 방식 모두 설명하려고 합니다.

 

 

위상정렬을 이용한 풀이

위상정렬에 대해서 모르시는 분은 아래 포스팅을 참고하시길 바랍니다.

 

 

위상정렬 Topological Sort (Java)

 

 

이 문제는 순서에 따라 진행되는 DAG 그래프이므로 위상정렬을 적용할 수 있습니다.

1번부터 N번까지 인접리스트를 사용하여 연결 관계를 명시하고, indegree 배열을 정의하여 위상정렬을 세팅해 줍니다.

 

이제, 모든 작업을 완료하기 위한 시간을 구해야 하는데, 각각의 작업을 수행하는 데 걸리는 시간을 int[] 타입의 result로 정의하였습니다.

 

처음에 이 result 에는 각각의 작업을 수행하는 데 걸리는 시간을 차례대로 세팅해 줍니다.

그리고 위상정렬을 실행하면서 result[next] = max(result[next], result[now] + time[next]) 을 취하여 연속적으로 초기화 합니다.

여기서, now는 큐에서 방금 꺼낸 작업이고, next는 now와 연결된 다음 작업을 의미합니다.

 

위와 같은 점화식을 사용하는 이유는, 이전에 모든 작업이 끝나지 않으면 다음 작업을 수행할 수 없기 때문에 최장거리를 구한다고 생각하시면 됩니다.

 

가령, C 작업을 수행하기 위해서 A와 B 작업이 선행되어야 한다고 가정해 봅시다.

이 때, A 작업이 10초, B 작업이 20초 걸린다고 하면, 결과적으로 C 작업을 수행하기 위해서는 20초가 필요하다는 사실을 알 수 있습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드 - 풀이1

 

 

DP를 이용한 풀이

위상정렬에서 사용한 점화식을 다시 봅시다.

 

 

result[next] = max(result[next], result[now] + time[next])

 

 

각각의 작업마다 가장 긴 수행 시간으로 설정해야하므로 위 점화식을 사용하였습니다.

그리고 문제의 조건이 DAG이므로 위상정렬을 사용하였지만, 사실 위상정렬을 쓰지 않고도 이 문제를 풀 수 있습니다.

 

문제의 입력값을 보면, 맨 앞에 수행 시간이 주어지고 뒤에는 선행되는 작업의 목록이 주어집니다.

우리는 입력값을 하나씩 받으면서 위 점화식을 사용하여 bottom-up을 하면 됩니다.

 

아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드 - 풀이2

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.