[백준] 1948 임계경로 C++

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

 

---

후기

TopologySort + 탐색(DFS, BFS)가 같이 들어가 조금 어려웠던 문제 입니다.

일단 문제를 읽고 위상정렬이라는 것 자체를 떠올리기가 힘들었고 역으로 1분도 쉬지 않고 달려야하는 경로를 찾는부분도 해맸던 문제입니다.

---

해설

먼저 문제의 조건에서 사이클이 없다는 것과 가장 마지막에 도착하는 사람이 있다는 것을 기반으로 위상정렬 아이디어를 떠올려서 가장 마지막에 도착하는 사람의 도착시간을 구해줍니다.

(저는 스타크래프트 배럭과 벙커를 예시로 생각했습니다... 벙커를 지을려면 배럭을 먼저 지어야 하는 식의 예시)

이후 도착점으로 부터 출발지 까지 역으로 DFS든 BFS로든 탐색을 해주는데

'다음으로 갈 노드의 결과 값' == '현재 결과값 + 비용' 과 같다면 탐색을 진행하고 그렇지 않다면 탐색을 하지 않음으로써 시간 복잡도를 줄여나가며 1분도 쉬지 않고 가야하는 경로 카운팅을 해줍니다.

---

코드 

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <queue>
#include <limits.h>
#include <memory.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;

#define endl "\n"
#define ll long long

int n, m;
int startDosi, endDosi;
vector<vector<pair<int, int>>> adj;
vector<int> parent;
vector<int> indegree;
vector<int> ret;
queue<int> q;
int goal = 0;
int totalPathCount = 0;

vector<vector<pair<int, int>>> radj;
vector<bool> visit;

void DFS(int now)
{
	if (visit[now]) return;
	visit[now] = true;
	for (auto next : radj[now])
	{
		int nn = next.first;
		int nc = next.second;
		if (ret[now] == ret[nn] + nc)
		{
			DFS(nn);
			++totalPathCount;
		}
	}
}

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

	cin >> n;
	cin >> m;

	adj.resize(n + 1, vector<pair<int, int>>());
	radj.resize(n + 1, vector<pair<int, int>>());
	parent.resize(n + 1);
	ret.resize(n + 1);
	indegree.resize(n + 1);
	visit.resize(n + 1);

	for (int i = 1; i <= n; ++i)
	{
		parent[i] = i;
	}

	for (int i = 1; i <= m; ++i)
	{
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		radj[b].push_back(make_pair(a, c));
		++indegree[b];
	}
	cin >> startDosi >> endDosi;

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

	while (!q.empty())
	{
		int now = q.front(); q.pop();
		for (auto next : adj[now])
		{
			int nn = next.first;
			int nc = next.second;
			ret[nn] = max(ret[nn], ret[now] + nc);
			if (--indegree[nn] == 0) q.push(nn);
		}
	}

	goal = ret[endDosi];
	DFS(endDosi);

	cout << goal << endl;
	cout << totalPathCount << endl;

	return 0;
}