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

 

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

1948번: 임계경로

---

문제

---

접근 방식

 

두가지 방법으로 풀어보았다.

1. 시작점과 끝점에서 BFS
2. 위상정렬

1.

시작점에서 BFS를 하여 목적지까지의 최대 거리와 각각의 지점까지 최대 거리를 구한다.

그 후 끝 점에서부터 다시 BFS를 하며, 

현재까지의 거리 - 지나갈 간선 = 지나갈 곳의 거리 <-이 식을 만족하면, 그 간선은 쉬지않고 간 간선이라는 뜻이므로 이러한 간선들의 숫자를 세준다.

이 방법에서 중요한 점은 , 이미 지나간 간선을 처리해야 다시 간선을 방문하였을 때 탐색을 하지 않는다.

 

2.

위상정렬을 통해서 목적지 까지의 최대 거리를 구한 후, 다시 목적지에서부터 시작하여

이미 지나온곳이 쉬지 않은 곳 이고, 위의 공식을 만족하면 그 다음 곳 또한 쉬지 않고 간다는 뜻이므로 숫자를 세준다.

 

---

첫 번째 방법

#include <iostream>
#include<queue>
#include<vector>
#include<tuple>
using namespace std;
int n, m, s, e;
vector <pair<int,int>> v[100001];//길
vector<tuple<int, int, int>> rev[100001];
int d[100001];
bool flag[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y,z});
		rev[y].push_back({ x,z,i });

	}
	cin >> s >> e;
	queue<pair<int, int>> q;
	q.push({ s,0 });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] < y + v[x][i].second) {
				d[v[x][i].first] = y + v[x][i].second;
				q.push({ v[x][i].first,v[x][i].second + y });
			}
		}
	}
	cout << d[e] << '\n';
	int counter = 0;
	q.push({ e, d[e] });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < rev[x].size(); i++) {
			if (!flag[get<2>(rev[x][i])] && d[get<0>(rev[x][i])] == y - get<1>(rev[x][i])) {
				flag[get<2>(rev[x][i])] = true;
				counter++;
				q.push({ get<0>(rev[x][i]) ,y - get<1>(rev[x][i]) });
			}
		}
	}
	cout << counter;
}

---

두 번째 방법

#include <iostream>
#include<queue>
#include<vector>
#include<tuple>
#include<cmath>
using namespace std;
int n, m, s, e;
vector <pair<int, int>> v[100001];//길
vector<pair<int,int>> rev[100001];
int d[100001];
bool flag[100001];
int inDegree[10001];
int outDegree[10001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({ y,z });
		rev[y].push_back({ x,z });
		inDegree[y]++;
		outDegree[x]++;
	}
	cin >> s >> e;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int x = q.front();
		q.pop();	
		for (int i = 0; i < v[x].size(); i++) {
			int dis = v[x][i].second;
			int next = v[x][i].first;
			d[next] = max(d[next], d[x] + dis);
			inDegree[next]--;
			if (inDegree[next] == 0)q.push(next);
		}
	}
	cout << d[e] << '\n';
	int counter = 0;
	flag[e] = true;
	q.push(e);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < rev[x].size(); i++) {
			int next = rev[x][i].first;
			int dis = rev[x][i].second;
			if (flag[x] && d[x] - dis == d[next]) {
				counter++;
				flag[next] = true;
			}
			outDegree[next]--;
			if (outDegree[next] == 0)q.push(next);
		}
	}
	cout << counter;
}

---

밑에가 첫번째 방법,위에가 두번째 방법이다.

확실히 위상정렬을 통해서 해결한게 시간적으로 훨씬 줄었는데, BFS를 통한 방법은 간선을 검사하는 과정에서 이미 지나온 간선을 다 확인하는 반면, 위상정렬을 통한 방법은 한 간선은 한번만 확인을 하기 때문에 차이가 크게 나는것으로 보인다.

1번째 방법도 예외처리를 더 한다면 시간이 줄어들겠지만 ,,, 방법을 찾지 못하겠다.