궤도
[백준] 10217번 : KCM Travel 본문
문제
풀이
지금까지 풀었던 골드1 문제는 힌트를 조금씩 봐야했는데, 이건 정말 나혼자만의 힘으로 풀었다. 뿌듯히다.
처음에는 '플로이드-워셜'일까 싶었는데 이것도 모든 경로와 비용을 고려하진 못해서 동적 계획법을 써야겠거니 했다.
일단 최소 2차원 배열일 것 같았고, 행과 열을 무엇으로 할지 고민했는데 냅색 문제를 떠올렸다.
그래서 행을 각 정점으로 하고, 열을 비용으로 하는 2차원 dp 배열을 생각했다. 예제 입력 1의 두번째 테스트 케이스에 대해서 dp 배열의 초기값을 만들어보면
이렇게 될 것이다.
dp[i(파란색)][j(초록색)]의 의미는 j만큼의 비용이 있을 때 1번 정점에서 i번 정점까지 가는 최단 거리이다.
당연히 출발점인 1에서 1까지 가는 최단거리는 비용에 상관없이 0이다.
한편 예제 입력 1의 그래프를 그려보면
이런 모습이다.
첫번째는 비용, 두번째는 거리다.
그냥 보통의 다익스트라를 생각해보자.
1에서 2번 정점과 3번 정점을 갈 수 있는데, 2번 정점까지의 거리가 3으로 더 짧으니 2번 정점을 먼저 확인할 것이다.
이 때 1->2의 비용은 0+5=5, 거리는 0+3=3이다.
기존의 dp[2][5]과 비교하면 INF>3으로 갱신이 가능하다. 그러므로 dp[2][5] 부터 dp[2][10]까지 살펴보며 3보다 크다면 전부 3으로 갱신해준다.
다음으로 선택된 간선은 1->3인 간선이다. 비용은 10, 거리는 6이다. 아까와 같은 방법으로 갱신하면
이렇게 된다.
다음으로 선택된 간선은 2->3인 간선이다. 비용은 5, 거리는 4이다.
이 간선을 쓸 때, 1->3의 비용은 5+5=10, 거리는 3+4=7이다.
이는 dp[3][10]의 값인 6보다 큰 값이므로 갱신하지 않는다.
다음으로 선택된 간선은 3->4인 간선이다. 비용은 1, 거리는 5이다.
아까와 같이 계산하면 비용은 10+1=11, 거리는 6+5=11일 수도 있고 7+5=12일 수도 있다.
뭐가 됐든 최대 비용인 M을 넘어서기 때문에 갱신할 수 없다.
마지막으로 dp[4][10]을 보면 여전히 INF이기 때문에 10의 비용으론 4까지 갈 수 없다는 것을 알 수 있다.
이 예제만 보면 풀이가 와닿지 않을 수도 있으니 비슷하지만 조금 다른 예제를 남기겠다.
1
4 11 4
1 2 5 3
2 3 4 4
3 4 1 5
1 3 10 6
output : 11
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> tp;
const int INF = 1e9;
vector<vector<tp>> graph;
vector<vector<int>> dp; //dp[i][j] = j의 비용으로 갈 수 있는 1->i의 최단거리
int dijkstra(int start, int end, int M) {
priority_queue<tp, vector<tp>, greater<tp>> pq;
for (int i = 0; i <= M; i++) //나 자신까지의 거리는 비용에 상관없이 0
dp[start][i] = 0;
pq.push(make_tuple(0, 0, start));
while (!pq.empty()) {
int cur_dist = get<0>(pq.top()); //현재 정점까지의 거리
int cur_cost = get<1>(pq.top()); //현재 정점까지의 비용
int cur = get<2>(pq.top()); //현재 정점
pq.pop();
for (int i = 0; i < graph[cur].size(); i++) {
int dest = get<0>(graph[cur][i]); //목적지
int new_dist = cur_dist + get<2>(graph[cur][i]); //start 정점에서 목적지까지의 거리
int new_cost = cur_cost + get<1>(graph[cur][i]); //start 정점에서 목적지까지의 비용
if ((new_cost <= M) && (dp[dest][new_cost] > new_dist)) { //비용이 M 이하이고, 기존의 최단거리보다 짧다면
int tmp = new_cost;
while ((tmp <= M) && (dp[dest][tmp] > new_dist)) { //갱신할 수 있는 곳까지 갱신
dp[dest][tmp] = new_dist;
tmp++;
}
pq.push(make_tuple(new_dist, new_cost, dest)); //우선순위 큐에 삽입
}
}
}
return dp[end][M]; //M의 비용으로 갈 수 있는 1->end의 최단거리
}
int main() {
int T, N, M, K, u, v, c, d;
cin >> T;
for (int t = 0; t < T; t++) {
cin >> N >> M >> K;
graph.assign(N + 1, vector<tp>(0));
dp.assign(N + 1, vector<int>(M + 1, INF)); //NxM
for (int i = 0; i < K; i++) {
cin >> u >> v >> c >> d;
graph[u].push_back(make_tuple(v, c, d));
}
int result = dijkstra(1, N, M);
if (result == INF)
cout << "Poor KCM\n";
else
cout << result << '\n';
}
}전체 소스코드다.
typedef tuple<int, int, int> tp;
const int INF = 1e9;
vector<vector<tp>> graph;
vector<vector<int>> dp; //dp[i][j] = j의 비용으로 갈 수 있는 1->i의 최단거리저장할게 많아서 튜플을 쓰겠다.
cin >> N >> M >> K;
graph.assign(N + 1, vector<tp>(0));
dp.assign(N + 1, vector<int>(M + 1, INF)); //NxM
for (int i = 0; i < K; i++) {
cin >> u >> v >> c >> d;
graph[u].push_back(make_tuple(v, c, d));
}입력받은대로 잘 초기화하고
int result = dijkstra(1, N, M);다익스트라를 실행한다.
int dijkstra(int start, int end, int M) {
priority_queue<tp, vector<tp>, greater<tp>> pq;
for (int i = 0; i <= M; i++) //나 자신까지의 거리는 비용에 상관없이 0
dp[start][i] = 0;
pq.push(make_tuple(0, 0, start));
while (!pq.empty()) {
int cur_dist = get<0>(pq.top()); //현재 정점까지의 거리
int cur_cost = get<1>(pq.top()); //현재 정점까지의 비용
int cur = get<2>(pq.top()); //현재 정점
pq.pop();
for (int i = 0; i < graph[cur].size(); i++) {
int dest = get<0>(graph[cur][i]); //목적지
int new_dist = cur_dist + get<2>(graph[cur][i]); //start 정점에서 목적지까지의 거리
int new_cost = cur_cost + get<1>(graph[cur][i]); //start 정점에서 목적지까지의 비용
if ((new_cost <= M) && (dp[dest][new_cost] > new_dist)) { //비용이 M 이하이고, 기존의 최단거리보다 짧다면
int tmp = new_cost;
while ((tmp <= M) && (dp[dest][tmp] > new_dist)) { //갱신할 수 있는 곳까지 갱신
dp[dest][tmp] = new_dist;
tmp++;
}
pq.push(make_tuple(new_dist, new_cost, dest)); //우선순위 큐에 삽입
}
}
}
return dp[end][M]; //M의 비용으로 갈 수 있는 1->end의 최단거리
}기존의 다익스트라와 거의 비슷하다.
1차원 배열이었던 min_dist를 2차원으로 확장해서 dp로 쓰는 정도?
priority_queue<tp, vector<tp>, greater<tp>> pq;
for (int i = 0; i <= M; i++) //나 자신까지의 거리는 비용에 상관없이 0
dp[start][i] = 0;
pq.push(make_tuple(0, 0, start));시작 정점에 따라 dp배열을 초기화 한다.
while (!pq.empty()) {
int cur_dist = get<0>(pq.top()); //현재 정점까지의 거리
int cur_cost = get<1>(pq.top()); //현재 정점까지의 비용
int cur = get<2>(pq.top()); //현재 정점
pq.pop();
for (int i = 0; i < graph[cur].size(); i++) {
int dest = get<0>(graph[cur][i]); //목적지
int new_dist = cur_dist + get<2>(graph[cur][i]); //start 정점에서 목적지까지의 거리
int new_cost = cur_cost + get<1>(graph[cur][i]); //start 정점에서 목적지까지의 비용
if ((new_cost <= M) && (dp[dest][new_cost] > new_dist)) { //비용이 M 이하이고, 기존의 최단거리보다 짧다면
int tmp = new_cost;
while ((tmp <= M) && (dp[dest][tmp] > new_dist)) { //갱신할 수 있는 곳까지 갱신
dp[dest][tmp] = new_dist;
tmp++;
}
pq.push(make_tuple(new_dist, new_cost, dest)); //우선순위 큐에 삽입
}
}
}그리고 while 문을 돌면서 dp를 갱신할 것이다.
int cur_dist = get<0>(pq.top()); //현재 정점까지의 거리
int cur_cost = get<1>(pq.top()); //현재 정점까지의 비용
int cur = get<2>(pq.top()); //현재 정점
pq.pop();cur이 이번에 확인할 정점이라고 할때
cur_dist는 1->cur의 거리, cur_cost는 1->cur의 비용이다.
for (int i = 0; i < graph[cur].size(); i++) {
int dest = get<0>(graph[cur][i]); //목적지
int new_dist = cur_dist + get<2>(graph[cur][i]); //start 정점에서 목적지까지의 거리
int new_cost = cur_cost + get<1>(graph[cur][i]); //start 정점에서 목적지까지의 비용
if ((new_cost <= M) && (dp[dest][new_cost] > new_dist)) { //비용이 M 이하이고, 기존의 최단거리보다 짧다면
int tmp = new_cost;
while ((tmp <= M) && (dp[dest][tmp] > new_dist)) { //갱신할 수 있는 곳까지 갱신
dp[dest][tmp] = new_dist;
tmp++;
}
pq.push(make_tuple(new_dist, new_cost, dest)); //우선순위 큐에 삽입
}
}연결된 모든 정점을 확인하자.
int dest = get<0>(graph[cur][i]); //목적지
int new_dist = cur_dist + get<2>(graph[cur][i]); //start 정점에서 목적지까지의 거리
int new_cost = cur_cost + get<1>(graph[cur][i]); //start 정점에서 목적지까지의 비용cur에서 갈 수 있는 목적지 dest와 그 dest로 가는 거리와 비용이다.
if ((new_cost <= M) && (dp[dest][new_cost] > new_dist)) { //비용이 M 이하이고, 기존의 최단거리보다 짧다면
int tmp = new_cost;
while ((tmp <= M) && (dp[dest][tmp] > new_dist)) { //갱신할 수 있는 곳까지 갱신
dp[dest][tmp] = new_dist;
tmp++;
}
pq.push(make_tuple(new_dist, new_cost, dest)); //우선순위 큐에 삽입
}만약 이 new_cost가 M 이하이며 dp[dest][new_cost]의 값보다 new_dist가 작다면 갱신할 수 있는 것이다.
그러므로 while문을 돌며 갱신할 수 있을 때까지 갱신하고, 큐에 넣어준다.
return dp[end][M]; //M의 비용으로 갈 수 있는 1->end의 최단거리마지막으로 리턴하면 끝
if (result == INF)
cout << "Poor KCM\n";
else
cout << result << '\n';결과는 이렇게 출력한다.
