[백준 1005] ACM Craft

1단계: 문제 이해

 

2 //테스트 케이스 2번
4 4 // 건물의 개수 4개 , 건설순서의 규칙 개수 4개
10 1 100 10 //1번건물 :10 2번건물:1 3번건물:100 4번건물:10
1 2 // 1번건물 지은다음 2번건물 지을 수 있음
1 3 // 1번건물 지은다음 3번건물 지을 수 있음
2 4 // 2번건물 지은다음 4번건물
3 4 // 3번건물 지은다음 4번건물
4 // 승리하기 위해 4번건물을 지어야 함, 건물 4를 완료하는데 드는 최소 시간을 출력
8 8 
10 20 1 5 8 7 1 43
1 2 //1번=>2번
1 3 //1번=>3번
2 4 //2번=>4번
2 5 //2번=>5번
3 6 //3번=>6번
5 7 //5번=>7번
6 7 //6번=>7번
7 8 //7번=>8번
7 //7번이 짓는데 걸리는 최소시간

첫번째 케이스

4번이 건물을 지을려면 2번과 3번 건물을 지어야한다.

2번을 지을려면 1번이 지어져야한다

3번을 지을려면 1번이 지어져야한다

최소시간으로 구해야한다.

즉

여기서 뭔가 위상정렬 느낌이 난다.

왜냐하면 어떤 일을 수행하기 위해 우선선행조건을 해야하기 때문이다.

위상정렬은 비순환 방향그래프(DAG)에서 정점을 선형으로 정렬

모든 간선(u,v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬 할 수가 있다

즉 그림으로 표현을 한다면

---

 

문제해결

 

위상정렬을 통해 건물을 방문하면 건물순서규칙을 지키면서 모든 건물에 방문 할 수가 있다.

2번케이스를 보자.

1,2,3,4,5,6,7,8번 순으로 방문이 될것이다.

진입차수가 0인 1번건물을 큐에 넣고 그 큐에 빼서 1번이 연결하고 있던 2번건물과 3번건물의 건물시간을 갱신해야한다. 여기선 1번건물이 10분이 걸리므로 2번건물 짓는시간은 20분, 3번건물 1분이다.

1단계)

처음 시작 1번건물을 새로운 배열에 10분을 새롭게 갱신한다.

2단계)

1번건물에의해서 2번건물20분이 지어질때 총 30분이므로 새롭게 2번건물에 대한 다른 배열에 갱신한다

또한 1번건물에 의해서 3번건물이 지어지므로 총 11분이므로 새롭게 3번건물에대한 배열에 갱신한다.

3단계)

이제 2번건물과 3번건물이 진입차수가 0이므로 큐에 넣어지고 그 큐에서 2번건물을 빼고나서

2번건물이 연결하고 있던 4번건물(5분)을 지면 이 4번건물에 35분이 갱신된다. 그러고 4번건물이 진입차수가 0이므로 큐에넣어진다.

또한 2번건물이 연결하고 있던 5번건물(8분)을 지으면 이 5번건물에 38분이 갱신된다.

그러고 5번건물의 진입차수가 0이므로 큐에 넣어진다.

4단계)

이제 3번 건물을 빼고나서 3번건물이 연결하고 있던 6번 건물(7분)을 18분으로 갱신한다.

그리고 6번건물의 진입차수가 0이므로 큐에 넣어진다.

5단계)

이제 큐에서 4번건물을 빼는데 연결된 건물이 없으므로 종료한다

6단계)

다음으로 큐에서 5번건물을 뺀다 이 5번건물에 연결해있던 7번건물을 갱신한다 39분으로

하지만 진입차수가 아직 1이므로 큐에 안넣는다.

7단계)

다음으로 큐에서 6번건물을 뺀다. 6번건물에 연결해있던 7번건물을 갱신한다. 19분인데 이미 39분으로 갱신되있던거랑 비교해서 큰게 저장되므로 39분으로 갱신되고 7번건물을 진입차수가 0이므로 큐에 7건물을 집어넣는다.

8단계)

큐에서 7번건물이 빼지는데 목표건물과 같으므로 7번건물에 저장된 시간인 39분이 정답으로 제출한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

int N, K;//건물개수, 규칙수

int buildTime[1001];

//건물 짓는 규칙
vector<int> rule[1001];

//진입차수
int inDegree[1001];

//목표 건물
int W;

//목표 값
long long timeRes[1001];


long long topologySort() {
	
	queue<int> q;

	for (int i = 1; i <= N;i++) {
		if (inDegree[i] == 0) {
			
			q.push(i);
			//처음에 진입차수가 0인 건물들을 모두 timeRes에 갱신시킴
			timeRes[i] = buildTime[i];
		}
	}

	for (int i = 1; i <= N; i++) {
		
		int x = q.front();

		//큐에 빠진게 목표건물이라면 끝
		if (x == W) break;

		q.pop();
		for (int j = 0; j < rule[x].size(); j++) {
			//진입차수가 0인 x건물과 연결된 건물 y
			int y = rule[x][j];
			//y건물이 짓는데 걸리는 시간+이전까지 걸렸던 시간
			timeRes[y] = max(timeRes[y], buildTime[y] + timeRes[x]);

			//새롭게 진입차수가 0이된 건물을 큐에 삽입
			if (--inDegree[y] == 0)
				q.push(y);
		}
		
			

	}
	return timeRes[W];
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		
		//건물 시간 초기화
		memset(buildTime, 0, sizeof(buildTime));
		memset(inDegree, 0, sizeof(inDegree));
		memset(timeRes, -1, sizeof(timeRes));
		//벡터 초기화
		for (int i = 1; i <= N; i++) {
			rule[i].clear();
		}
		
		cin >> N >> K;

		//건물 짓는데 걸리는 시간
		for (int i = 1; i <= N; i++)
		{
			cin >> buildTime[i];

		}
		//규칙 
		for (int i = 0; i < K; i++)
		{
			int a, b;
			cin >> a >> b;
			rule[a].push_back(b);
			inDegree[b]++;
		}

		cin >> W;

		long long result = topologySort();

		cout << result << '\n';

	}
}