BOJ 14461 - 소가 길을 건너간 이유 7 [C++]

https://www.acmicpc.net/problem/14461

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

문제 요약

2차원 격자판이 주어지고, 각 칸에는 정수가 주어진다.

칸에서 상하좌우로 이동할 수 있으며 한 번의 이동에는 $T$의 시간이 소모된다.

이동을 3번 하고 나면, 풀을 먹어야 해서(?) 현재 칸에 쓰여있는 정수만큼의 시간이 더 걸린다.

$(1,1)$에서 $(N,N)$으로 이동하는데 걸리는 최소 시간을 구하는 문제이다.

 

문제 해결

state를 구성하는 요소는 크게 세 가지이다.

1. 풀을 먹은 후에 몇 번의 이동을 했는가? $ = t$

2. 지금까지 오는 데 시간이 얼마나 걸렸나? $ = time$

3. 현재 위치는 어디인가? $ = (x,y)$

 

가중치가 다른 그래프에서의 특정한 두 점간의 최단 경로를 구하는 문제로 생각할 수 있다. 즉, 다익스트라를 적용할 수 있다.

방문 여부 배열은 3차원 배열 [100][100][3]로 나타낼 수 있다. 각각 $x, y, t$를 의미한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, T;
    cin >> N >> T;
    int arr[101][101]{};
    for (int i = 1; i <= N; i++)	for (int j = 1; j <= N; j++)	cin >> arr[i][j];

    int vis[101][101][3]{};
    int dx[4] = { 1,0,-1,0 };
    int dy[4] = { 0,1,0,-1 };

    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<>> Q;

    vis[1][1][0]++;
    Q.emplace(0, 1, 1, 0);
    while (!Q.empty()) {
        auto [time, x, y, t] = Q.top();
        Q.pop();
        if (x == N && y == N) {
            cout << time;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 1 && xx <= N && yy >= 1 && yy <= N && !vis[xx][yy][(t + 1) % 3]) {
                vis[xx][yy][(t + 1) % 3]++;
                int next_time = time + T;
                if ((t + 1) % 3 == 0)	next_time += arr[xx][yy];
                Q.emplace(next_time, xx, yy, (t + 1) % 3);
            }
        }
    }

}