백준 16118 - 달빛 여우(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16118

16118번: 달빛 여우

다익스트라를 사용하는 문제였습니다.

달빛 여우와 늑대가 어느 정점을 갈 때의 최소 비용이 여우가 더 적은 정점의 개수를 찾는 문제입니다.
주의할 점은 여우는 주어진 비용으로만 가지만, 늑대는 (비용/2) -> (비용*2) -> (비용/2) ..... 의 방법으로 가게 됩니다.

그렇다면 다른 정점까지의 여우의 최솟값, 늑대의 최솟값을 구한 뒤 이들을 비교해 답을 구해주면 됩니다.

여우의 최소 비용을 구하는 방법은 일반적인 다익스트라를 통해서 쉽게 구할 수 있습니다.
문제는 늑대의 최소 비용을 구하는 방법인데, 간단하게 생각하면은 한번은 /2 를 하고 다음번은 *2를 하는 방법을 하면 된다고 생각할 수 있습니다.

물론, /2 하고 *2를 하는 방법은 같지만, 생각해 봐야할 것이 있습니다.

해당 그래프를 본다면, 1->4까지의 경우가 문제가 됩니다.
늑대의 최소 비용은 7이 됩니다.
그렇지만, 정점의 최소 비용만을 가지고 찾게 된다면, 9.5라는 값을 저장하게 됩니다.
이는 1 -> 2가지 갔을 때의 최소 값은 1.5 이기 떄문에, 1 -> 4까지 가는 방법인 (1 -> 3 -> 2 -> 4)에서 1 -> 2의 값인 5를 저장하기 않기 때문입니다.
이를 해결하기 위해서는 어떤 정점을 들릴 때, 경우가 2가지 임을 찾을 수 있어야 합니다.
어떤 정점은 *2로 왔을 때, /2로 왔을 때, 2번이 있기에, 각각의 경우에 따라서 다른 최소 비용을 가지게 될 수 있습니다.
따라서, 배열을 [2][N]으로 만들어 2가지 경우의 최소 비용을 저장해주면 됩니다.


저는 문제를 풀 때, 2로 나눌 경우 소수가 나올 수 있기에 정점의 비용을 저장할 때, 2를 곱해서 저장해줬으며,
최소 비용을 저장한 배열은 [2][2][N]으로 만들어 여우 or 늑대 + (*2 or /2) + 정점으로 만들어 줬습니다.




자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second

using namespace std;

int N, M;
vector<pair<int, int>> connect[4001];
long long Distance[2][2][4001]; // (여우 / 늑대), 이동횟수(늑대만 사용), 정점
priority_queue<pair<long long, pair<int, int>>> q; //거리, 이동 횟수, 정점

void reset_distance(){
	for(int i = 0; i < 2; i++){
		for(int j = 1; j <= N; j++){
			Distance[i][0][j] = INF;
			Distance[i][1][j] = INF;
		}
	}
}

void Dijstra(int way){
	Distance[way][0][1] = 0;
	q.push({-0, {0, 1}});
	while(!q.empty()){
		int x = q.top().S.S;
		int num = q.top().S.F;
		long long cost = -q.top().F;
		q.pop();
		if(way == 0 && Distance[way][0][x] < cost) continue;
		if(way == 1 && Distance[way][num%2][x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			if(way == 0){
				long long n_cost = cost + connect[x][i].S;
				if(Distance[way][0][xx] > n_cost){
					Distance[way][0][xx] = n_cost;
					q.push({-Distance[way][0][xx], {num+1, xx}});
				}	
			}
			else{
				if(num % 2 == 0){ // 2배만큼 빠르게 갈 때
					long long n_cost = cost + connect[x][i].S / 2;
					if(Distance[way][(num+1)%2][xx] > n_cost){
						Distance[way][(num+1)%2][xx] = n_cost;
						q.push({-Distance[way][(num+1)%2][xx], {num+1, xx}});
					}	
				}	
				else{ // 2배만큼 느리게 갈 때
					long long n_cost = cost + connect[x][i].S * 2;
					if(Distance[way][(num+1)%2][xx] > n_cost){
						Distance[way][(num+1)%2][xx] = n_cost;
						q.push({-Distance[way][(num+1)%2][xx], {num+1, xx}});
					}	
				}
			}
		}
	}
}

void solve(){
	reset_distance();
	Dijstra(0);
	Dijstra(1);
	int ans = 0;
	for(int i = 1; i <= N; i++) {
		if(Distance[0][0][i] < min(Distance[1][0][i], Distance[1][1][i])){
			ans++;
		}
	}
	cout << ans;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost * 2});
		connect[y].push_back({x, cost * 2});
	}	
	solve();
	return 0;
}

질문 및 조언은 코드를 참고해주세요.