# KCM Travel - 10217

aliceshard·2022년 3월 16일
0

## 2. 코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <utility>
#define INF 0xFFFFFF
using namespace std;

class compare {
public:
bool operator()(const vector<int> e1, const vector<int> e2) {
// compare d
return e1[2] > e2[2];
}
};

int n, m, k, T = 0;
int memo[101][10001];
vector<vector<vector<int>>> graph;
priority_queue<vector<int>, vector<vector<int>>, compare> pq;

void dijkstra(int start) {
vector<int> tp_start = { 1, 0, 0 };
pq.push(tp_start);

while (pq.size() != 0) {
vector<int> temp = pq.top();
pq.pop();
int now = temp[0];
int fee = temp[1];
int dist = temp[2];

// prevent loop
if (memo[now][fee] < dist)
continue;

for (int i = 0; i < graph[now].size(); i++) {
vector<int> graph_ptr = graph[now][i];
int dest = graph_ptr[0];
int fee_next = graph_ptr[1];

int total_dist = dist + adj_dist;
int total_fee = fee + fee_next;

if (total_fee > m)
continue;
if (memo[dest][total_fee] <= total_dist)
continue;

for (int j = total_fee; j <= m; j++) {
if (memo[dest][j] > total_dist)
memo[dest][j] = total_dist;
}
pq.push({ dest, total_fee, total_dist });
}
}
}

int main(void) {
cin >> T;
for (int i = 0; i < T; i++) {
int ans = INF;
cin >> n >> m >> k;

// init.
graph.clear();
for (int j = 0; j < n + 1; j++) {
vector<vector<int>> tp1 = {};
graph.push_back(tp1);
}
for (int j = 0; j < 101; j++)
for (int l = 0; l < 10001; l++)
memo[j][l] = INF;

// store graph inputs
for (int j = 0; j < k; j++) {
int u, v, c, d = 0;
cin >> u >> v >> c >> d;
vector<int> tp = { v, c, d };
graph[u].push_back(tp);
}

dijkstra(1);

for (int j = 0; j <= m; j++) {
ans = min(ans, memo[n][j]);
}

if (ans == INF) {
printf("Poor KCM\n");
}
else {
printf("%d\n", ans);
}
}

return 0;
}

## 3. 풀이 메모

처음에는 우선순위큐에 넣는 객체를 pair로 <비용, 거리> 꼴로 같이 넣은 뒤, 다음과 같이 pq에 삽입 조건을 설정했다.

if ((total_dist < memo[dest].second || total_fee < memo[dest].first) && total_fee <= m)
{
memo[dest].second = total_dist;
memo[dest].first = total_fee;
vector<int> tp = { dest, total_fee, total_dist };
pq.push(tp);
}

그런데 이렇게 코드를 작성하면 이미 방문한 곳도 우선순위 큐에 들어가게 되는데, 그 과정에서 비효율적으로 동작하게 된다. 특히 IF문 내부에서 dist와 fee 둘 중 하나라도 기존 DP테이블에 저장된 값보다 작을 때 삽입되도록 설계되어 있는데, 다음과 같은 양방향 그래프로 정의된 특수한 상황을 고려해보자.

먼저, dist가 짧은 1->2가 우선적으로 고려되며, 이후 2->n이 처리되어 DP테이블에 n열에는 [8, 2]가 저장된다. 이후 1->3이 고려되며, 노드 n에 도달했을 때는 [6, 4]가 될 것이다. 이때, 노드 2에 저장된 DP 테이블 값은 [4, 1] 이기에, 우선순위 큐에는 결국 모든 n->2로 가는 간선이 또 다시 저장된다. 이는 노드3, 노드4에서도 마찬가지이며, 결국 모든 간선을 다 고려하는 것과 유사한 작동 양상이 된다.

인터넷에서 찾은 다른 방법은 2차원 배열을 기반으로 동적계획법을 사용하는 것인데, 그 방법이 (동적계획법이 늘 그렇듯이) 꽤 생소하다.

memo[목적지][비용(fee)]

다음과 같이 DP 테이블을 정의한다. 이렇게 정의된 memo[][] 내부를 이루는 원소는 거리(dist) 정보이다. 이 DP 테이블이 내포하고 있는 의미는 다음과 같다.

현재 "비용" 을 얼마나 갖고 있는가? "목적지" 까지 그 "비용" 으로는 갈 수 있는가?

예컨대 노드1에서 노드2까지 가는데는 최소 4의 비용이 필요하다. 따라서 4 이상의 예산을 갖고 있다면, 그 목적지까지는 갈 수 있다는 것이다. 여기서 다익스트라 알고리즘을 엮어서 해당 지점에 도달하는데 필요한 최소 거리(total_dist)에 대한 정보를 얻어내 memo[][] 내부에 저장하면, 결국 다음과 같은 정보를 저장하는 행렬을 얻게 된다.

그 "비용" 으로 "목적지" 까지 가는데 거치는 "최소 거리" 는 얼마인가?

이를 맞춰서 작성한 코드는 다음과 같다.

for (int j = total_fee; j <= m; j++)
{
if (memo[dest][j] > total_dist)
memo[dest][j] = total_dist;
}

total_fee 이상의 모든 열에 대해서 최소 거리를 넣으면서 초기화 해주면, 언제 어디서나 "저 비용 m만큼 있는데, 목적지 n까지 갈 수 있나요? 최소 거리는 어떻게 되나요?" 에 대한 물음에 답할 수 있게 된다.

## 4. 코멘트

다익스트라 알고리즘이라고 하긴 구조가 좀 다른 것 같다. 인터넷에 보면 트리 순회 문제로 분류하는 경우도 종종 볼 수 있다.

안녕하세요.