백준 1005 : ACM Craft

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

1005번: ACM Craft

 

어떠한 건물을 짓기 위하여 선행적으로 지어져야하는 건물들이 있으므로 위상 정렬 문제다.

이 문제의 경우 간선에 가중치가 있으므로 각 건물을 빌드하는데 걸리는 시간을 bfs를 돌면서 해당 위치에 도달하는데 걸리는 시간들 중 가장 오래 걸리는 시간 값으로 갱신해준다.

위상정렬은 O(V + E) 의 시간복잡도로 해결 가능하다. (V는 정점의 수, E는 간선의 수)

 

#include <iostream>
#include <vector>
#include <queue>

#define max(a,b) a>b?a:b
using namespace std;

int n, w;
int build_time[1001];

int bfs(vector<vector<int>>& edge, vector<int>& pre_cnt) {
	int cur, next;
	queue<int> q;
	int visited[1001] = { 0, };

	//선행 빌드가 없는 건물 큐에 삽입
	for (int i = 1; i <= n; i++) {
		if (!pre_cnt[i]) {
			q.push(i);
			visited[i] = build_time[i];
		}
	}

	while (!q.empty()) {
		cur = q.front();
		q.pop();

		//현재 정점이 w라면, 이미 선행 빌드를 모두 완료한 상태이고, 
		//시간 값이 갱신된 상태이므로 break
		if (cur == w) break;

		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			//간선에 가중치가 있으므로 더 먼저 도착한 쪽이 더 오래 걸릴 수 있다.
			//따라서 해당 위치에 도착하는 시간 중 가장 큰 값으로 한다.
			visited[next] = max(visited[next], visited[cur] + build_time[next]);
			//선행 빌드 개수 감소
			--pre_cnt[next];

			//더이상 선행 빌드가 없을 시 큐에 삽입
			if (!pre_cnt[next]) q.push(next);
		}
	}

	return visited[w];
}

void solution() {
	int t, k;
	int from, to;

	cin >> t;
	while (t--) {
		cin >> n >> k;

		int ans;
		vector<vector<int>> edge(n + 1, vector<int>());
		vector<int> pre_cnt(n + 1, 0);

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

		while (k--) {
			cin >> from >> to;
			edge[from].push_back(to);
			++pre_cnt[to];
		}
		cin >> w;

		ans = bfs(edge, pre_cnt);
		cout << ans << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2832 kb

시간: 168 ms