BOJ - 1005번 ACM Craft(C++)

문제 출처: https://www.acmicpc.net/problem/1005

문제 난이도

Gold 3 (solved.ac 이용)

문제 접근법

1. 앞서 간선으로 연결된 노드가 건설이 끝나야 다음 건설 작업을 할 수 있다.
2. 즉, 자신으로 오는 화살표가 사라지면 본인 작업을 할 수 있다 -> 진입 차수 계산
3. 그래서 위상정렬 원리를 사용해야한다는 결론이 된다.

위상 정렬은 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.

잊지 말아야 할 것!
진입 차수 0인 노드부터 시작한다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int cost[1001], build[1001];
int node[1001];

int solution(vector<int> craft[1001]) {
	int N, K, W;
	int result = 0;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> cost[i];
	}
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		craft[a].push_back(b);
		node[b]++;
	}
	cin >> W;
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (node[i] == 0) {
			q.push(i);
		}
		build[i] += cost[i];
	}
	for (int i = 1; i <= N; i++) {
		int x = q.front();
		q.pop();

		for (int next : craft[x]) {
			build[next] = max(build[next], build[x] + cost[next]);
			if (--node[next] == 0) {
				q.push(next);
			}
		}
	}
	return build[W];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		memset(cost, 0, sizeof(cost));
		memset(node, 0, sizeof(node));
		memset(build, 0, sizeof(build));
		vector<int> craft[1001];
		cout <<  solution(craft) << "\n";
	}
	return 0;
}

피드백

위상 정렬을 떠올리고 코드 작성한 거 까지는 좋았다. 맨 하단에 최대값을 구하는 거까지 이해해서 풀었으나, 처참하게 틀렸습니다가 떴다.

	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (node[i] == 0) {
			q.push(i);
		}
		if(node[i] == 0&& i == W) return cost[W];
	}
	result += cost[q.front()];
	while (!q.empty()) {
		int size = q.size();
		int maxV = 0;
		while (size--) {
			int x = q.front();
			q.pop();
			if (x == W) {
				break;
			}
			for (int i = 0; i < craft[x].size(); i++) {
				if (--node[craft[x][i]] == 0) {
					q.push(craft[x][i]);
					if (maxV < cost[craft[x][i]]) {
						maxV = cost[craft[x][i]];
					}
				}
			}
		}
		result += maxV;
	}
	return result;

이렇게 구성했으나 예제 입력2의 3번째 케이스 답이 틀렸었다. 값을 계산하지 못하는 노드가 생겼다. queue를 이용해도 노드 전체를 들릴거라 생각했으나 오류였다.
그래서 인터넷을 이용하게 됐고 배열을 이용한 걸 보고 다시 코드를 짰다...
위상정렬에서 노드 전체를 돌려야한다는 걸 잊지 말자!