[BOJ 9925 // C++] Scout Outing

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 9925번 문제인 Scout Outing이다.
문제는 아래 링크를 확인하자.

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

9925번: Scout Outing

입력으로 주어지는 그래프는 DAG이므로, 모든 노드를 위상정렬순으로 접근하는 것으로 T의 값을 계산해낼 수 있다.

 

또한 문제에 주어진 규칙과 같이 움직일 때 (출발 노드를 제외한) 각 노드에 scout들이 도착하는 가장 이른 시각과 가장 늦은 시각을 기록해두는 것으로 total waiting time을 계산해낼 수 있다.

 

어느 정도 지연출발을 하더라도 T에 영향을 주지 않을 수 있는 노드들은 "정확히 T의 시간을 소비해야 이동할 수 있는 경로"에 포함되지 않은 노드들과 같다. 정확히 T의 시간을 소비해야 이동할 수 있는 경로 위의 노드들은 "이동하자마자 다음 이동을 해야하는" 관계에 있는 에지들을 뒤집은 그래프에서 노드 N으로부터 접근 가능함을 이용해 문제를 해결해주자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
vector<pair<int,int>> G[101];
int indegree[101];
int dist[101];
int acc[101];
int totalwaiting;
int totaldelayed;

void bfs() {
	queue<int> que;
	que.push(1);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& p : G[cur]) {
			int nxt = p.first, w = p.second;
			dist[nxt] = max(dist[nxt], dist[cur] + w);
			acc[nxt] = min(acc[nxt], dist[cur] + w);
			indegree[nxt]--;

			if (indegree[nxt] == 0) que.push(nxt);
		}
	}
}

vector<int> GG[101];
bool visited[101];

void dfs(int cur) {
	visited[cur] = 1;
	for (auto& nxt : GG[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

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

	cin >> N >> M;
	while (M--) {
		int x, y, w; cin >> x >> y >> w;
		indegree[y]++;
		G[x].emplace_back(make_pair(y, w));
	}

	for (int n = 1; n <= N; n++) acc[n] = 1000000007;
	bfs();

	for (int n = 2; n <= N; n++) totalwaiting += dist[n] - acc[n];
	for (int n = 1; n < N; n++) {
		for (auto& p : G[n]) {
			int nxt = p.first, w = p.second;
			if (dist[n] + w == dist[nxt]) GG[nxt].emplace_back(n);
		}
	}

	dfs(N);

	for (int n = 1; n < N; n++) {
		if (!visited[n]) totaldelayed++;
	}
	cout << dist[N] << ' ' << totalwaiting << ' ' << totaldelayed;
}