[P5] 백준 1948번 임계경로 C++ 위상 정렬

리뷰

 

처참한 전투흔적.. 위상 정렬의 응용 문제였는데 꽤나 애를 먹었다.

최소 거리를 구하는 부분은 쉽게 나왔으나 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는게 어려웠다.

처음엔 거리 배열을 사용하여 max로 갱신될 경우 이전 경로로 교체를 해주고, 값이 같을땐 현재 저장된 거리에 새로 들어온 경로를 더해주는 방식으로 생각했었다.

하지만 이전까지 같은 경로로 오다 갈라진 후 다시 합쳐지는 케이스에서는 해당 방법을 사용할 수 없었다.

이후 set를 사용해 왔던 경로를 모두 저장해 준 뒤 set의 크기를 출력해 주었으나 메모리 초과가 났다.

결국 왔던 길을 역추적 해서 검증이 가능한 길의 개수만 구해지는 방식으로 풀이하였다.

해당 방식이 맞는 접근 방법이나, 중복이 가능한 케이스들을 놓쳐서 방문 처리를 하고 나니 통과하였다.

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

 

문제 풀이

1. 노드의 수 n, 간선의 수 m, 인접 간선의 수 cnt, 각 노드의 거리 dist, 방문 배열 v, 시작 노드 s, 도착 노드 e, 인접 리스트용 구조체 Edge, 정방향 인접 리스트 Edge 타입 벡터 path, rev_path를 전역 변수로 설정해 준다.
2. input 함수를 통해 n, m값을 입력 받고, path, rev_path를 n + 1크기로 초기화 해준다.
3. m개의 간선 정보를 받아와 정방향 인접 리스트path를 만들어 주고, 역방향 인접 리스트 rev_path를 만들어 준다.
4. 이후 시작 노드의 번호 s와 도착 노드의 번호 e를 입력 받아 준다.
5. solution 함수를 통해 정방향으로 탐색을 진행하며 도착 노드에 모이는 거리의 최소값과 각 노드의 거리를 구해준다.
6. 시작 노드부터 탐색을 시작하여 각 인접리스트를 순회하며 최대값을 갱신해 주고 cnt가 0이되면 큐에 노드를 넣는다.
7. 모든 노드의 cnt가 0이되어 큐가 빌때까지 탐색을 해주고 e의 최소 거리 정보를 출력해 주면 된다.
8. rev 함수를 통해 역방향으로 탐색을 진행하며 왔던길의 거리를 검증해 주고 일치하면 도로 개수를 증가시켜준다.
9. 다음 노드의 거리 + 해당 간선의 가중치가 현재 노드의 거리와 일치하다면 검증이 완료된 도로이다.
10. 이때 중복처리를 위해 한번 방문한 노드는 큐에 추가되지 않도록 해준다, 도로의 개수는 늘려줘야 한다.
11. 모든 탐색을 마치고 풀로 돌려야 하는 도로의 개수를 출력해 주면 된다.

 

참고 사항

예제 케이스는 엣지 케이스를 거르는데 전혀 도움이 되지 못한다. 오히려 혼란만 주는 느낌이니 적당한 크기의 예제 케이스를 만들어 돌려보는걸 추천한다.

 

 

정답 코드

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

using namespace std;
int n, m;
int cnt[10001] = { 0, };
int dist[10001] = { 0, };
int v[10001] = { 0, };
int s, e;

struct Edge {
	int node, w;
};

vector<vector<Edge>> path, rev_path;

void input() {
	cin >> n >> m;
	path.resize(n + 1);
	rev_path.resize(n + 1);
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		path[a].push_back({ b, c });
		rev_path[b].push_back({ a, c });
		cnt[b]++;
	}
	cin >> s >> e;
}

void solution() {
	queue<int> q; q.push(s);
	while (!q.empty()) {
		int cn = q.front(); q.pop();
		for (Edge edge : path[cn]) {
			int nn = edge.node, nw = edge.w;
			if (dist[nn] < dist[cn] + nw) dist[nn] = dist[cn] + nw;
			if (--cnt[nn] == 0) q.push(nn);
		}
	}
	cout << dist[e] << "\n";
}

void rev() {
	int back_cnt = 0;
	queue<int> q; q.push(e);
	while (!q.empty()) {
		int cn = q.front(); q.pop();
		for (Edge edge : rev_path[cn]) {
			int pn = edge.node, nw = edge.w;
			if (dist[pn] + nw == dist[cn]) {
				back_cnt++;
				if (!v[pn]) {
					v[pn] = 1;
					q.push(pn);
				}
			}
		}
	}
	cout << back_cnt;
}

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

	input();
	solution();
	rev();
}