Baekjoon 1005 ACM Craft

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

소스 결과 3440 KB / 304 ms

언어 C++ 17

출처 Baekjoon

분류 위상정렬, BFS

 

설명

최백준이 승리를 하여 여자친구 데이트를 할 수 있도록 도와주자

 

위상정렬에 관한 문제다. 위상 정렬을 하는 방법으로는 여러 방법이 있지만 Queue를 활용한 BFS와 유사한 방식으로 위상정렬을 진행한다.

 

알고리즘

1. 입력 받은 각 지점의 값을 기준으로 희소 인접 행렬을 구성한다.

2. 자신으로 들어오는 지점이 없는 점을 시작지점으로 판단하여 Queue에 push 한다.

3. Queue에 원소가 없을 때 까지 반복한다.

 3-1. 현재 지점으로 들어가는 노드가 있는지 판별한다.

 3-2. 현재 탐색하는 원소와 연결된 지점을 방문하고 시간을 계산한다.

 3-3. 계산된 시간이 최대 시간이면 현재 지점의 최대 시간을 갱신한다.

4. 목표 지점의 최대 시간을 출력한다.

 

소스코드

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

using namespace std;

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

	cin >> tcc;

	while (tcc--) {
		int n, k; cin >> n >> k;
		vector<int> time(n);
		vector<int> maxTime(n);
		vector<int> degree(n);
		vector<vector<int>> adj(n);
		queue <int> q;

		for (int i = 0; i < n; i++)
			cin >> time[i];

		for (int i = 0; i < k; i++) {
			int to, des; cin >> to >> des;
			adj[to - 1].push_back(des - 1);
			degree[des - 1]++;
		}

		int tar; cin >> tar;

		for (int i = 0; i < n; i++)
			if (!degree[i]) {
				q.push(i);
				maxTime[i] = time[i];
			}

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

			if (degree[cur] < 1) {
				for (int i = 0; i < adj[cur].size(); i++) {
					int next = adj[cur][i];
					int nextTime = maxTime[cur] + time[next];

					if (maxTime[next] < nextTime) {
						maxTime[next] = nextTime;
						q.push(next);
					}
					degree[next]--;

				}
			}
		}

		cout << maxTime[tar - 1] << '\n';
	}

	return 0;
}