백준 14461 - 소가 길을 건너간 이유 7(C++)

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

14461번: 소가 길을 건너간 이유 7

다차원 배열을 사용하는 다익스트라 문제입니다.

소가 길을 건널 때, 주어진 조건에 따라 최소 시간을 구하는 문제입니다.
(1, 1) ->(N, N)으로 가면서, 3번째 방문하는 곳은 항상 풀을 먹어야 합니다. 이동할 때마다 이동시간 T가 추가됩니다.

항상 최단 횟수로 갔을 때, 최소 비용이 나온다는 보장을 할 수 없습니다.(위의 예시가 그렇습니다.)
따라서 다익스트라를 통해 어느 정점에 들렸을 때, 최단 시간이 얼마인지를 저장해주면서 풀어야합니다.

여기서 주의할 점이 한 위치를 왔다고 했을 때, 1, 2번째로 들린 곳인지, 아니면 3번째로 들린 곳인지에 따라서 값이 달라진다는 점이 있습니다.
3번째로 들렸다면 풀을 무조건 먹어야하기에 이 경우를 나눠주지 않는다면, 풀을 먹은 값을 저장할 수 없을 것입니다.
따라서 3칸으로 나누어 몇번째로 들렸는지를 저장해줘야 합니다.

나머지는 조건에 따라 다익스트라를 구현하면 풀 수 있습니다.


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

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 9876543210000
#define F first
#define S second

using namespace std;

int N, T;
int map[101][101];
long long Distance[101][101][3]; // 위치를 1,2,3번째로 들릴 때마다 값이 달라야 됨으로 3칸을 만든다.
int dx[4] = {1, 0, -1, 0}; // 하, 우, 상, 좌
int dy[4] = {0, 1, 0, -1};
priority_queue<pair<pair<long, int>, pair<int, int>>> q; //시간, 몇번에 왔는지, 좌표(X, Y)

void reset_distance(){ // 처음에 모든 값을 큰 값으로 초기화 한다.
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			for(int k = 0; k < 3; k++){
				Distance[i][j][k] = INF;
			}
		}
	}
}

void Dijstra(pair<int, int> st){
	reset_distance();
	Distance[st.F][st.S][0] = 0;
	q.push({{-0, 0}, st});
	while(!q.empty()){
		int x = q.top().S.F;
		int y = q.top().S.S;
		int cnt = q.top().F.S;
		long long dis = -q.top().F.F;
		q.pop();
		if(Distance[x][y][cnt] < dis) continue; //이전에 저장된 값보다 큰 값이면 확인할 필요가 없음
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= N){ //map범위 안에 있으며
				if(cnt + 1 == 3){ //다음으로 가야하는 곳이 풀을 먹아야하는 곳이면
					long long n_dis = dis + T + map[xx][yy];
					if(Distance[xx][yy][0] > n_dis){
						Distance[xx][yy][0] = n_dis;
						q.push({{-n_dis, 0}, {xx, yy}});
					}
				}
				else{ //다음에 갈 곳이 풀을 먹지 않아도 된다면
					long long n_dis = dis + T;
					if(Distance[xx][yy][cnt+1] > n_dis){
						Distance[xx][yy][cnt+1] = n_dis;
						q.push({{-n_dis, cnt+1}, {xx, yy}});
					}
				}
			}
		}
	}
}

void solve(){
	Dijstra({1, 1});
	long long sum = INF;
	for(int i = 0; i < 3; i++){
		sum = min(sum, Distance[N][N][i]);
	}
	cout << sum;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> T;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.