BOJ 1948 - 임계경로 (위상정렬)

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

작업 https://suuntree.tistory.com/119문제의 응용

 

<문제설명>

DAG(무사이클방향그래프)임이 보장됨.

시작점 ~ 도착점까지 최장거리를 구하고, 그 경로를 모두 칠했을 때 칠해진 간선의 수를 구하는 문제.

 

<풀이>

최장거리를 구하고 d배열 초기화 하는 것은 '작업' 문제와 동일함. 

 

경로를 칠하는 것은 역방향 으로 정점을 순회하면서 d[next] = d[curr]+ weight(curr~next) 인 경우만 dfs로 따라가 주면 된다. 

 

백준님의 그림

위 그림은 예제를 그대로 그린 것이다. 최장 경로는 12이므로, (7,2) 간선은 포함되지 않는다.

 

유의할 점은 이미 방문된 정점을 재 방문 하는 경우가 생긴다는 것이다.

 

위 예제에서 (7,2) 간선도 유효한 간선이라고 가정해보자. 그러면 dfs 순서는 7->(2->1) -> (6->4->1) ....이 되는데,  일반적인 dfs론 (6,2) 간선을 체크하지 못한다. 따라서, 방문했던 정점이라도 일단 재방문 할 수 있게 처리(cnt++)하되

그 정점이 방문됐던 적이 있다면 바로 리턴하도록 해야 한다.

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P;
const int MAX = 1e4 + 4;

int n, m, ind[MAX], d[MAX], st, en;
vector<P> adj[MAX], radj[MAX];

bool chk[MAX] = { false };
int cnt = 0;
void dfs(int curr) {
	if (chk[curr]) return;
	chk[curr] = true;

	for (P p : radj[curr]) {
		int next = p.first, w = p.second;
		if (d[curr] == d[next] + w) {
			dfs(next);
			cnt++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;
	for (int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		ind[v]++;
		adj[u].push_back({ v,w });
		radj[v].push_back({ u,w });
	}
	cin >> st >> en;

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (ind[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int curr = q.front(); q.pop();
		for (P p : adj[curr]) {
			int next = p.first, w = p.second;
			if (d[next] < d[curr] + w) {
				d[next] = d[curr] + w;
			}

			if (--ind[next] == 0) q.push(next);
		}
	}

	//작업문제와 다른부분은 이부분뿐
	dfs(en);

	int ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, d[i]);
	cout << ans << '\n' << cnt << '\n';
}

 

<생각>

dfs에서 간선을 다루는 법에 대해서 생각할 수 있었던 문제였다.

 

다익스트라 문제에서도 경로를 칠하는 문제가 나오면 같은 로직을 쓰면 될 것 같다