[공학]전치그래프,

소개글

n개의 task들로 구성된 프로젝트가 있다. 이들 task를 수행하는데 걸리는 시간이 주어지고, 또한 이들 task 사이의 선후관계가 주어진다.

1) 이때, 이 프로젝트의 task들을 선후관계를 만족하면서 모든 task들을 순서대로 수행하려고 한다. 이를 만족하는 task들의 수행 순서들 중 하나를 출력하라. 만약 이러한 순서가 존재하지 않으면 “수행순서가 존재하지 않음”을 출력한다.

2) 임계경로(임의의 하나)를 구하고, 이 프로젝트를 완료하는데 걸리는 최단시간을 출력하라.

목차

□ 문제정의
□ 문제 해결방법
□ 수행결과
□ 결 론

본문내용

1. 테스트 케이스는 전체적으로 3부분으로 나누어지는데, 첫 번째는 일의 개수고, 두 번째는 순차적으로 일들의 수행시간이다. 마지막으로 세 번째는 각 일들간의 선후관계이다. 이것을 메모리에 저장을 하게 되는데, 두 번째 부분인 일들의 수행시간은 time 이라는 배열에 저장을 한다. 그리고, 선후관계는 Linked List를 이용하여 표현한다. 하지만 우리가 사용할 것은 전치그래프이므로 들어오는 값을 반대로 한다.
While(true)
{
fin >> tmp1 >> tmp2;
if(fin.fail())
break;
ptr = new NodeType;
ptr->vertex = tmp1;
ptr->link = adjV[tmp2];
adjV[tmp2] = ptr;

ptr2 = new NodeType;
ptr2->vertex = tmp2;
ptr2->link = adjV2[tmp1];
adjV2[tmp1] = ptr2;
}
예를 들어 9의 값과 1의 값이 들어온다면 선후관계는 9 1이 된다. 하지만 우리는 전치그래프를 이용할 것이므로 9의 값과 1의 값이 들어온다면 선후관계는 1 9이 된다. 즉, 반대로 된다는 것이다.
이런 식으로 전치그래프를 만든다.

2. 전치그래프에서 시작하는 시작정점은 원래 그래프의 맨 마지막의 값이다. 이 말은 원래 그래프에서 null의 값을 가지고 있는 노드를 찾으면 되는 것이다. 그래서 위에서 소스와 마찬가지로 원래 그래프를 하나 더 생성하여 null의 값을 가지고 있는 시작 정점을 찾는다.

참고 자료

없음