c++/알고리즘

[C++] 백준 - 11779 최소비용구하기2 (다익스트라)

hojung 2023. 2. 15.

728x90

1. 문제

2. 입출력 및 예제

3. 문제 해설

백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다.

하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다.

처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다.

하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다.

여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익스트라 알고리즘을 이용해서 푸는 문제이기 때문에 greedy알고리즘을 기반으로 한다. 즉, 한번 이 노드가 최소 값으로 갱신됐으니 다시 살펴보지 않는다는 전제하에 앞으로의 경로를 탐색하는 것이다.

나는 처음에 한 도시에서 다른 도시로 이동할 때 한 개의 루트만 존재할 수 있는 줄 알았다. 따라서 방문처리에 대한 부분은 신경쓰지 않은 채 그저 다익스트라 알고리즘을 이용해 진행했고 결과는 시간초과였다.

만약 1번 도시에서 2번 도시로 갈 수 있는 길이 2개이고 그 cost가 각각 10과 2였다면 다익스트라 알고리즘을 통해 목적지가 2이고 cost가 10인 길을 먼저 탐색할 것이다. 그렇게 되면 1번 노드에서 2번 노드로 가는 길을 10으로 한 것이 priority_queue안에 들어갈 것이다.

pq 안에는 {node : 2, cost : 10}; 가 먼저 들어간다.

그 다음 탐색하는 것이 목적지가 2이고 cost가 2인 길일 것이다. 이 경우에도 기존에 목적이 2번의 거리가 앞서 10으로 업데이트 된 값보다 작으므로 pq안에 들어가게 된다.

pq안에는 {node:2 , cost: 10} , {node : 2, cost : 2}가 들어가지만 pq의 특성 상 다음과 같이 정렬이 될 것이다.

pq : {node :2, cost : 2} , {node : 2, node : 10}

이렇게 되면 2번 노드부터 꺼내서 다시 다익스트라 알고리즘을 수행한다.

하지만 그 다음 노드 또한 노드 2번에 해당한다. 만약 이 노드에 대해 또 다익스트라 알고리즘을 수행해준다면 우리는 사실상 결과에는 영향을 주지 않는(어차피 처음에 업데이트 된 값이 최단경로일테니...(pq의 성질에 의해)) 쓸데없는 다익스트라 알고리즘을 수행하게 되는 것이다. 따라서 다음과 같은 처리가 필요하다.

if(dist[curr.node] < curr.cost) continue; // 이미 방문을 한 노드에 대해서는 더 이상 진행하지 않고 넘긴다.

경로 처리

우리가 일반적으로 사용하는 다익스트라 알고리즘은 pq를 이용해 다음과 같이 구현된다.

vector<n_t>AL[MAX]; // 간선 정보가 들어있는 인접리스트
void dijkstra(int root) {
	priority_queue<n_t> pq;
    dist[root] = 0;
    pq.push({root,0});
    while(pq.size()) {
    	n_t curr = pq.top(); pq.pop();
        if(dist[curr] < curr.cost) continue; // 방문 처리
        for(n_t next : AL[curr.node]) {
        	int cost = dist[curr.node] + next.cost;
            if(dist[next.node] > cost) {
            	dist[next.node] = cost;
                pq.push({next.node, cost});
            }
        }
    }
}

위의 다익스트라 알고리즘에서 최단 경로를 갱신하는 부분은 바로 다음과 같다.

int cost = dist[curr.cost] + next.cost
if(dist[next.node] > cost) {
	dist[next.node] = cost;
    pq.push({next.node, cost});
}

이 부분에서 어떤 일이 생기는 지 살펴보면 next.node로 이동할 때 기존의 이동경로보다 curr에서 이동하는 것이 더 짧은 경로니까 갱신해줘! 라는 뜻이다. 따라서 next를 가기 전은 무조건 curr을 거쳐 간다는 것을 알 수 있다. 따라서 나는 다음과 같이 이전 경로를 기억해주었다.

int dist[MAX];
vector<n_t> AL[MAX];
int prevPath[MAX];
vector<int> path;
int root, leaf;
void dijkstra(int root) {
	priority_queue<n_t> pq;
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	} // 무한대로 초기화
	
	dist[root] = 0;
	pq.push({ root, 0 });
	while (pq.size()) {
		n_t curr = pq.top(); pq.pop();
		if (dist[curr.node] < curr.cost) continue;
		for (n_t next : AL[curr.node]) {
			int cost = dist[curr.node] + next.cost;
			if (dist[next.node] > cost) {
				dist[next.node] = cost;
				prevPath[next.node] = curr.node;
				pq.push({ next.node, cost });
			}
		}
	}
}

그렇다면 prevPath라는 배열에는 현재 경로로 도착하기 전 어디서 왔는가에 대한 정보가 저장될 것이다. 그렇다면

거꾸로 따라가면 된다.

예제를 돌려 prevPath와 dist를 출력해보면 다음과 같다.

예제에서 1번에서 5번으로 가는 길을 출력하라 했으므로 prePath[5]번부터 살펴본다. 4에 해당한다. 4번에서 왔다는 것이다.

그러면 다시 prevPath[4]를 확인한다. 4는 어디서 왔을까? -> prevPath[4] = 1이므로 1에서 온 것을 확인할 수 있다.

그렇다면 1로 이동한다. prePath[1] = 0이다. 시작점이라는 뜻이다. 따라서 종료한다. 이 과정에서 몇 개의 도시를 거쳤는 지 경로는 어디인지 모두 확인할 수 있다. 나는 코드를 다음과 같이 구성했다.

4. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <vector>
#include <queue>
#define MAX 1001
#define BUSMAX 100001
#define INF 0x3f3f3f3f
using namespace std;

int n, m;
struct n_t {
	int node;
	int cost;

	inline bool const operator < (const n_t& ref) const {
		return this->cost > ref.cost;
	}
};
int dist[MAX];
vector<n_t> AL[MAX];
int prevPath[MAX];
vector<int> path;
int root, leaf;
void input() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int s, e, c;
		scanf("%d %d %d", &s, &e, &c);
		AL[s].push_back({ e,c }); //인접리스트 생성
	}
}

void dijkstra(int root) {
	priority_queue<n_t> pq;
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	} // 무한대로 초기화
	
	dist[root] = 0;
	pq.push({ root, 0 });
	while (pq.size()) {
		n_t curr = pq.top(); pq.pop();
		if (dist[curr.node] < curr.cost) continue;
		for (n_t next : AL[curr.node]) {
			int cost = dist[curr.node] + next.cost;
			if (dist[next.node] > cost) {
				dist[next.node] = cost;
				prevPath[next.node] = curr.node;
				pq.push({ next.node, cost });
			}
		}
	}
}
int cnt = 1;
int main() {

	input();
	scanf("%d %d", &root, &leaf);
	dijkstra(root);
	/*printf("distance --\n");
	for (int i = 1; i <= n; i++) {
		printf("%d ", dist[i]);
	}
	printf("\n");
	printf("prevPath --\n");
	for (int i = 1; i <= n; i++) {
		printf("%d ", prevPath[i]);
	}
	printf("\n");*/
	int idx = leaf;
	path.push_back(leaf);
	while (1) {
		if (prevPath[idx] == 0) break;
		cnt++;
		path.push_back(prevPath[idx]);
		idx = prevPath[idx];
	}
	printf("%d\n%d\n",dist[leaf], cnt);
	for (int i = path.size() - 1; i >= 0; i--) {
		printf("%d ", path[i]);
	}
	return 0;
}