백준 1005 c++ "ACM Craft" -PlusUltraCode-

https://www.acmicpc.net/problem/1005

 

[필자 사고]

이 문제는 위상정렬 문제이다.

다른 위상정렬 문제와 다른 이 문제만의 특이점은 아래와 같다.

 

자신이 걸리는 건물의 시간과

이 건물을 짓기 위한 그 동안의 시간을 더해야 된다는 점이다.

 

필자는 자신이 걸리는 건물의 시간은 마지막에 더하는 방식으로 진행하였따.

그 동안의 시간을 더하는 방식은 max함수를 이용하여 더 오래 걸리는 건물시간을 우선순위로 정했다.

 

아래는 소스코드 해설이다.

 

 

• 초기화 및 입력 처리:
  • initVec(int N) 함수는 각 벡터(makeTime, dCount, linkArr, resultTime)를 크기 N+1N+1N+1로 초기화합니다.
  • 입력 함수 Input()은 각 테스트 케이스에 대해 프로젝트 개수 NNN과 관계 수 KKK를 입력받습니다.
  • makeTime 배열은 각 노드(프로젝트)의 수행 시간을 저장합니다.
  • 이후, KKK개의 관계를 입력받아 선행 작업 관계를 linkArr에 저장하고, 선행 작업 수를 dCount에 기록합니다.
• BFS 함수:
  • BFS() 함수는 큐 myQueue를 이용해 위상 정렬을 수행합니다.
  • 선행 작업이 없는 노드(= dCount[i]가 0인 노드)를 큐에 삽입하여 탐색을 시작합니다.
  • 큐에서 노드를 하나씩 꺼내며, 해당 노드에서 연결된 다음 노드들의 선행 작업 수를 감소시킵니다.
  • 각 노드에 도달하는 최장 시간을 계산하고, 만약 선행 작업 수가 0이 되면 다음 노드를 큐에 삽입합니다.
• 결과 계산:
  • 입력이 끝난 후, 최종 목표 노드에 대해 resultTime과 makeTime을 이용해 해당 작업을 완료하는 데 걸리는 최장 시간을 출력합니다.

 

 

[소스 코드]

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

int T;
int N, K;
vector<int> makeTime;
vector<int> dCount;
vector<vector<int>> linkArr;
vector<int> resultTime;

void initVec(int N) {
	makeTime.clear();
	makeTime.resize(N + 1);
	dCount.clear();
	dCount.resize(N + 1);
	linkArr.clear();
	linkArr.resize(N + 1);
	resultTime.clear();
	resultTime.resize(N + 1);
}

void BFS() {

	queue<int> myQueue;
	for (int i = 1; i <= N; i++) {
		if (dCount[i] == 0) {
			myQueue.push(i);
		}
	}

	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();

		for (int nextIdx : linkArr[nowIdx]) {
			dCount[nextIdx]--;
			resultTime[nextIdx] = max(resultTime[nowIdx] + makeTime[nowIdx], resultTime[nextIdx]);

			if (dCount[nextIdx] == 0) {

				myQueue.push(nextIdx);

			}
		}
	}

}


void Input() {
	for (int t = 0; t < T; t++) {
		cin >> N >> K;
		
		initVec(N);

		for (int i = 1; i <= N; i++) {
			cin >> makeTime[i];
		}
		

		for (int i = 0; i < K; i++) {
			int a, b;
			cin >> a >> b;
			linkArr[a].push_back(b);
			dCount[b]++;
		}
		BFS();
		int end;
		cin >> end;
		cout << resultTime[end] + makeTime[end] << '\n';

	}

}





int main(void) {
	cin >> T;
	Input();
}