[백준 1005] ACM Craft (C++)

문제 링크: https://www.acmicpc.net/problem/1005

1005번: ACM Craft

1. 주의할 점

- 전역변수로 선언된 배열들을 잘 초기화해줘야 한다 (While문의 중간에 break걸리면 Pre값이 0으로 초기화가 안된다)

- DP, DFS, 다익스트라(BFS)를 사용하지 않는다 -> 안되는 TC가 있거나 TLE가 발생할 수 있다

- ~~가 선행되어야 한다 -> 위상정렬을 이용한다

- 1번 건물부터 시작한다는 보장이 없다

- 건물 짓는 순서가 번호순대로 들어온다는 보장이 없다

- 찾고자 하는 건물번호의 Pre값이 0일 수도 있다

 

2. 구현

- Pre 배열이 0이면 선행되어야 하는 건물이 없으므로 그 건물의 번호와 값을 우선순위큐에 넣는다

- 우선순위큐에서 1개씩 빼면서 해당 건물을 선행으로 삼고 있는 건물 번호의 Pre값을 1 감소 시킨다. 이후, Pre값이 0이면 우선순위큐에 해당 건물번호와 값을 넣는다

- Target번호가 나올때까지 반복한다

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
int arr[1001];	//해당 건물만을 짓는데 걸리는 시간
int pre[1001];		//해당 건물을 짓기 위해 선행으로 지어져야 하는 건물의 수
vector<int> v[1001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, result, node, edge, s, e, target;
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> node >> edge;
		result = 0;
		for (int i = 1; i <= node; i++) {
			cin >> arr[i];
			v[i].clear();
			pre[i] = 0;
		}
		for (int i = 0; i < edge; i++) {
			cin >> s >> e;
			v[s].push_back(e);
			pre[e]++;
		}
		cin >> target;
		if (pre[target] == 0) {
			cout << arr[target] << '\n';
			continue;
		}
		priority_queue<info, vector<info>, cmp> pq;
		for (int i = 1; i <= node; i++) {
			if (pre[i] == 0) {
				tmp.idx = i;
				tmp.val = arr[i];
				pq.push(tmp);
			}
		}
		while (!pq.empty()) {
			int cidx = pq.top().idx;
			int cv = pq.top().val;
			pq.pop();
			for (int i = 0; i < v[cidx].size(); i++) {
				int next = v[cidx][i];
				pre[next]--;
				if (pre[next] == 0) {
					int nv = cv + arr[next];
					if (next == target) {
						result = nv;
						break;
					}
					tmp.idx = next;
					tmp.val = nv;
					pq.push(tmp);
				}
			}
		}
		cout << result << '\n';
	}
	system("pause");
	return 0;
}