[백준] 1005번 ACM Craft

문제: 1005번: ACM Craft

 

처음 풀이(오답)

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

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

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, k; // n: 건물의 개수, k: 규칙의 총 개수
		cin >> n >> k; 

		// 건물 번호는 1번부터 N 번이니까 n+1 만큼 잡음(0번 인덱스는 안 쓸 것)
		vector<vector<int>> linkedList(n + 1);
		vector<int> inDegree(n + 1); // 각 정점의 진입 차수 저장
		vector<int> time(n + 1);

		// 그래프에서 자신을 뺐을 때, 영향을 받은 다른 노드의 진입 차수가 0이 되면 걔들을 queue 에 저장함
		// 그 중에서 건설 시간이 제일 큰 값을 nextMax 에 저장해놓을것
		// 그래서 나중에 queue 에서 값을 빼다가 nextMax 랑 값이 같아지면 그제서야 totalTime 에 더해줄 것.
		// queue 의 요소의 타입은 pair<pair<int, int>, int>
		// pair<int, int> 는 이전 정점과, 자신 정점 저장
		// Pair<pair<int, int>, int> 이렇게 해서 건설 시간 함께 저장
		vector<int> nextMax(n + 1); // 얘도 0번 인덱스에 맨 처음부터 진입 차수가 없던 노드 중 가장 건설 시간이 많이 걸리는 애 넣어놓을 것
		int totalTime = 0;


		for (int j = 1; j < n + 1; j++) {
			cin >> time[j]; // 1번부터 n번까지 건설 시간 저장
		}

		// 연결 정보 입력 받기
		for (int j = 0; j < k; j++) {
			int x, y; // x 를 지은 다음에 y 를 짓는 것이 가능하다는 의미라고 문제에서 줌
			cin >> x >> y;
			linkedList[x].push_back(y); // x 가 가리키는 정점으로 y 추가
			inDegree[y]++; // 진입 차수 +1 해주기
		}

		// 승리하기 위해 건설해야 할 건물의 번호 W
		int w;
		cin >> w;


		// 맨 처음 진입차수가 0인 정점들 queue 에 저장해주기
		queue<pair<pair<int, int>, int>> noInNodes;
		int maxTime = -1;
		for (int i = 1; i < n + 1; i++) {
			// 맨 처음 진입차수가 0인 애들은 이전 정점이 없으니까 이전 정점번호 0으로 저장해주기..
			if (inDegree[i] == 0) {
				noInNodes.push(make_pair(make_pair(0, i), time[i]));
				if (time[i] > maxTime) maxTime = time[i];
			}
		}
		nextMax[0] = maxTime; // 맨 처음부터 진입 차수가 없던 애들 중 가장 긴 건설 시간을 인덱스 0에 저장..


		while (!noInNodes.empty()) {
			pair<pair<int, int>, int> node = noInNodes.front();
			noInNodes.pop();

			int prevNode = node.first.first;
			int curNode = node.first.second;
			int curNodeTime = node.second;

			if (nextMax[prevNode] == curNodeTime) {
				totalTime += curNodeTime; // 가장 오래 걸리는 시간과 같으면 최종 시간에 더해주기
			}

			if (curNode == w) break; // 만약 현재 건설한 노드가 승리하기 위해 건설해야 하는 노드와 같다면 그냥 while 종료

			maxTime = -1;
			// 그래프에서 한 정점을 뺐을 때, 이와 연결되어 있던 정점 중 진입 차수가 0이 되면 stack 에 넣어주기
			for (int i = 0; i < linkedList[curNode].size(); i++) {
				int linkNode = linkedList[curNode][i];
				inDegree[linkNode]--;

				if (inDegree[linkNode] == 0) {
					if (maxTime < time[linkNode])
						maxTime = time[linkNode];
					noInNodes.push(make_pair(make_pair(curNode, linkNode), time[linkNode]));
				}
			}
			nextMax[curNode] = maxTime;
		}

		cout << totalTime << "\n";
	}

	return 0;
}

 

---

 

정답 풀이

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

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

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, k; // 건물의 수, 건설 순서 규칙의 총 개수
		cin >> n >> k;

		vector<int> time(n + 1); // 건물 번호는 1부터 시작해서 n+1 만큼 잡음(0번 인덱스 안 쓸 것)
		vector<vector<int>> linkedList(n + 1);
		vector<int> conTime(n + 1); // n 번 건물까지 건설 하는데 걸리는 시간(dp 테이블)
		vector<int> inDeg(n + 1); // 진입 차수 저장

		for (int j = 1; j < n+1; j++) {
			cin >> time[j]; // 건설 시간 입력 받기
		}

		for (int j = 0; j < k; j++) {
			int x, y; // 건설 순서: x 를 지은 다음에 y 를 짓는 것이 가능하다
			cin >> x >> y;
			linkedList[x].push_back(y); // 연결 정보 저장
			inDeg[y]++; // 진입 차수 +1 해주기
		}

		int w; // 건설해야 할 건물의 번호 w
		cin >> w;

		// 진입 차수가 0인 노드들 저장
		queue<int> noIndegNode;
		for (int i = 1; i < n + 1; i++) {
			if (inDeg[i] == 0) {
				noIndegNode.push(i);
				conTime[i] = time[i]; // 자기 자신만 건설하는데 걸리는 시간
			}
		}
		
		while (!noIndegNode.empty()) {
			int node = noIndegNode.front();
			noIndegNode.pop();

			// 현재 노드가 가리키는 노드들의 진입차수 -1 해주고, 만약 진입차수가 0이되면 noIndegNode 에 넣기
			for (int next : linkedList[node]) {
				// 정점 next 까지 건설하는 데 걸리는 시간은 기존 시간과 현재 새로 계산한 값중 큰 값으로..
				conTime[next] = max(conTime[next], conTime[node] + time[next]);

				inDeg[next]--;
				if (inDeg[next] == 0) noIndegNode.push(next);
			}
		}

		cout << conTime[w] << "\n"; // w 번 건물을 건설 완료하는데 드는 최소 시간
	}


	return 0;
}

 

그냥 dp 를 이용하면 쉽게 풀리는 문제였다. 어떤 건물을 짓기 위해서는 이 건물을 가리키고 있는 건물들이 모두 지어져야 한다. 

 

어떤 건물을 지을 때 이가 가리키고 있는 건물을 짓는데 걸리는 시간을 어떻게 결정하냐면 이미 계산되어 있는 시간과 현재 계산으로 나온 값을 비교해서 더 큰 값으로 해주는 것이다.

 

왜냐하면 해당 건물을 짓기 위해서는 이전 건물들이 다 지어져야 한다고 했는데 이전 건물들이 지어지는데 걸리는 시간은 그 중 가장 큰 시간과 같다. 왜냐하면 건물을 동시에 지을 수 있다고 했기 때문이다.

 

그래서 현재 짓는 건물이 가리키고 있는 건물을 짓는데 걸리는 시간은 일단 conTime[현재노드] + time[다음노드] 인데 이 값이 conTime[다음노드] 값 보다 크다면 갱신해주면 되는 것이다.

 

이번에 다시 깨닫게 된거지만 확실히 dp 에 많이 약한 것 같다. 애초에 dp 를 쓸 생각도 못한게 정말;; 시험 문제로 나올수도 있으니까.... 계속 복습해야겠다. 

 

 

 

참고자료:

[C++] 백준 1005번 탈출 — For Better Code Tomorrow

[C++] 백준 1005번 탈출

 

https://chatgpt.com/share/67403b13-2f08-8003-b022-547f38fc9800

ChatGPT