[문제]
N개의 작업공정이 있다. 공정마다 소요되는 시간이 존재하고, 각 공정들 끼리 관계가 존재할 때는 선행 공정이 끝나야만 다음공정으로 넘어갈 수 있다.
예를 들어 아래 공정을 보면, A공정에 10이 소요되고 난 후, B와 C가 동시에 진행이 된다. 그렇게되면 B공정이 끝나는 시점은 30이되고, C공정은 110에 끝나게 된다.
D공정은, B와 C가 모두 끝나는 시점인(=C가 끝나는 시점) 110에 시작하게 되고, 따라서 D공정은 130에 끝나게 된다.
이러한 원칙을 적용해서, 임의로 주어지는 공정에 대해 목표되는 공정까지 소요되는 최소시간을 구하시오.
입력
첫 째줄에 문제 개수 T가 나오고, 그 다음 줄에 공정수(N)와 관계수(R)이 나온다.
그 다음 줄에 각 공정에서 소요되는 시간 N개가 나오고, 그 다음 줄 부터 공정간의 관계가 R줄에 걸쳐 나온다.
공정간의 관계는 연결되는 공정 번호가 "앞공정번호 뒷공정번호" 순으로 나온다.
그 다음 줄에 목표되는 공정 번호가 나온다.
예를 들어, 위에서 설명한 공정의 경우에 대한 입력은 다음과 같다.
1
4 4
10 20 100 20
1 2
1 3
2 4
3 4
4
출력
문제 한개당 한 줄씩, 최소 소요시간을 출력한다.
ex)
130
[풀이]
문제에서 예로 든 공정 그림을 아래와 같이, 각 공정마다 가장 빨리 시작할 수 있는 시간(Early Start)과 가장빨리 끝낼 수 있는 시간(Early Finish)을 손으로 표시해보자. (공정 위쪽에, 왼쪽은 ES, 오른쪽은 EF)
손으로, 위 그림의 ES, EF의 계산할 때 본능적으로 A공정에서 시작해서 오른쪽으로 가면서 계산했을 것이다.
그렇지만 각 공정의 ES를 정할 때는, 연결된 이전 공정의 EF들을 고려하면서 정해야한다. 즉, 공정D의 관점에서 보면, 앞 공정들 B,C의 EF중에서 가장 큰값이 D공정이 시작할 수 있는 ES가 된다.
마찬가지로 B공정의 ES는, 연결된 이전공정인 A의 EF인 10이되고 EF=10+20=30이 되겠다.
C공정의 ES는 역시 A공정의 EF인 10이되고 EF=10+100=110이 되겠다.
A공정은 이전 공정이 없으므로 EF는 A공정의 소요시간인 10이 된다.
이와같이, 푸는 과정을 생각해보면, 목표되는 공정에서부터 시작해서 왼쪽방향에 연결된 공정들(선행공정들)에 대해 EF를 계산해나가다가, 선행공정이 없는 공정에서 EF=t가되는 것으로 종료를 하면 됨을 알 수 있겠다. 즉, 다이나믹 프로그래밍이 가능함을 알겠다.
다이나믹 프로그래밍에 맞게 수식을 만들어 보자.
먼저, 표현식에 대한 정의
- Node : 각 공정을 Node라는 객체로 보자 (각 공정마다 가질 수 있는 선행공정수가 가변이어서, 객체 사용하기로 함)
- 각 Node가 가지는 값은,
. t : 해당 공정의 소요시간
. ef: 해당 공정의 EarlyFinish 시간
. precedences: 해당 공정의 선행공정들
수식은,
수식1) Node[i].ef = Max{Node[i].precedences들의 ef } + Node[i].t , when Node[i].precedences.size > 0
수식2) Node[i].ef = t , when Node[i].precedences.size == 0
각 공정별로 선행공정들의 수가 가변이므로, 배열로 표현하기가 불편해서, Node라는 클래스를 만들어서 사용하자.
이 클래스는 소요시간 t와 EarlyFinish값을 가지고, 또한 선행공정들을 가지게 된다. 이러한 클래스를 만들면 다음과 같다.
static class Node {
int t, earlyFinish;
Vector<Node> precedences = new Vector<Node>();
public Node(int t) {
this.t = t;
earlyFinish = 0;
}
public void addPrecedence(Node n) {
precedences.add(n);
}
}
이 클래스에, 다이나믹 수식이 적용되는 getEF()라는 메서드를 만들자.
public int getEF(){
if(precedences.size() == 0){
earlyFinish = t;
return earlyFinish;
}
Enumeration<Node> e = precedences.elements();
Node node = null;
int max = 0;
int val = 0;
while (e.hasMoreElements()) {
node = e.nextElement();
if(node.earlyFinish == 0){
val = node.getEF();
}else{
val = node.earlyFinish;
}
if (val > max)
max = val;
}
earlyFinish=max+t;
return earlyFinish;
}
위 소스를 보면, 수식2에 해당하는 precedences가 없을 때 earlyFinish=t로 만드는 과정이 있고,
선행공정들(precedences)가 있는 경우는, 각 선행공정들의 earlyFinish중에서 가장 큰 값을 찾아내서, 현 공정의 earlyFinish값으로 치환하고 있다. 또한, 반복되는 재귀호출을 방지해서 효율화를 꾀하기 위해, earlyFinish값이 이미 계산된 공정에 대해서는 새로 계산하지 않고 사용하도록 되어 있다.
전체 내용은 아래쪽 전체소스 참조.
[소스]
문제 입력용 파일 input.txt
2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7
import java.io.File;
import java.util.Enumeration;
import java.util.Scanner;
import java.util.Vector;
public class ShortestDuration {
// public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(new File("input.txt"));
// Scanner sc = new Scanner(System.in);
int T, N, K, W;
T = sc.nextInt();
for (int testNum = 0; testNum < T; testNum++) {
N = sc.nextInt(); // 건물개수
K = sc.nextInt(); // 규칙
// 건축소요시간
int[] t = new int[N]; // time for construction
for (int i = 0; i < N; i++) {
t[i] = sc.nextInt();
}
// 규칙
int[][] r = new int[K][2]; // rule of schedule
for (int i = 0; i < K; i++) {
r[i][0] = sc.nextInt();
r[i][1] = sc.nextInt();
}
// Target
W = sc.nextInt();
int d = findShortestDuration(t, r, W);
System.out.println("" + d);
}
}
private static int findShortestDuration(int[] t, int[][] r, int tgt) {
// Node 객체 생성
Node[] nodes = new Node[t.length];
for (int i = 0; i < t.length; i++) {
nodes[i] = new Node(t[i]);
}
// 연결망 set
for (int i = 0; i < r.length; i++) {
nodes[r[i][1] - 1].addPrecedence(nodes[r[i][0] - 1]);
}
return nodes[tgt-1].getEF();
}
static class Node {
int t, earlyFinish;
Vector<Node> precedences = new Vector<Node>();
public Node(int t) {
this.t = t;
earlyFinish = 0;
}
public void addPrecedence(Node n) {
precedences.add(n);
}
public int getEF(){
if(precedences.size() == 0){
earlyFinish = t;
return earlyFinish;
}
Enumeration<Node> e = precedences.elements();
Node node = null;
int max = 0;
int val = 0;
while (e.hasMoreElements()) {
node = e.nextElement();
if(node.earlyFinish == 0){
val = node.getEF();
}else{
val = node.earlyFinish;
}
if (val > max)
max = val;
}
earlyFinish=max+t;
return earlyFinish;
}
}
}
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| 23. [다이나믹]옷 (0) | 2015.04.24 |
|---|---|
| 22. [다이나믹]배낭 문제 (Knapsack problem) (0) | 2015.04.21 |
| 20. [다이나믹] 행렬 경로 문제 (0) | 2015.04.16 |
| 19. [다이나믹]피보나치 수열 (0) | 2015.04.14 |
| 18. [다이나믹]파스칼의 삼각형 (0) | 2015.04.14 |