BOJ 4971 - Twirling Robot 링크
(2024.05.13 기준 G1)

문제

$h \times w$ 크기의 격자에서 맨 왼쪽 위 칸에 로봇이 동쪽을 바라보고 서있다. 각 격자마다 로봇이 수행할 명령이 적혀 있으며, 우리가 따로 비용을 내고 명령을 내릴 수 있다.

로봇이 맨 오른쪽 밑 칸에 가기 위한 최소 비용 출력

알고리즘

다익스트라

풀이

로봇은 네 방향 중 한 방향을 바라보고 있다. 또한 명령은 방향을 바꾸는 명령들이다.
그러므로 각 위치를 네 방향으로 쪼갠 그래프에서의 다익스트라 문제가 된다.

간단한 구현 문제이기 때문에 코드를 참고하자.

코드

• C++

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

typedef pair<int, int> pii;
typedef tuple<int, int, int, int> tiiii;

const int MAX = 30, inf = 1e8;
const pii dir[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 동, 남, 서, 북

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int w, h, s[MAX][MAX], c[4], dist[MAX][MAX][4];
    priority_queue<tiiii, vector<tiiii>, greater<tiiii>> pq;
    for (cin >> w >> h; w; cin >> w >> h){
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> s[i][j];
        for (int i = 0; i < 4; i++) cin >> c[i];

        // 각 칸에 각 방향으로 도착했을 때의 최적값을 다익스트라로 구하자.
        pq.push({0, 0, 0, 0});
        fill(&dist[0][0][0], &dist[h - 1][w - 1][4], inf);
        dist[0][0][0] = 0;
        while (!pq.empty()){
            auto [cost, i, j, d] = pq.top(); pq.pop();
            if (dist[i][j][d] < cost) continue;
            for (int command = 0, nxt_cost, nxt_d, nxt_i, nxt_j; command < 4; command++){
                if (s[i][j] == command) nxt_cost = cost; // 명령을 따로 내릴 필요 없다.
                else nxt_cost = cost + c[command]; // 명령을 따로 내려야 한다.
                nxt_d = (d + command) % 4; // 다음 방향
                nxt_i = i + dir[nxt_d].first; nxt_j = j + dir[nxt_d].second; // 다음 위치
                if (0 <= nxt_i && nxt_i < h && 0 <= nxt_j && nxt_j < w && dist[nxt_i][nxt_j][nxt_d] > nxt_cost){
                    dist[nxt_i][nxt_j][nxt_d] = nxt_cost;
                    pq.push({nxt_cost, nxt_i, nxt_j, nxt_d});
                }
            }
        }

        // 목적지에는 어느 방향으로든 도착만 하면 된다.
        cout << min({dist[h - 1][w - 1][0], dist[h - 1][w - 1][1], dist[h - 1][w - 1][2], dist[h - 1][w - 1][3]}) << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush

dir = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 동, 남, 서, 북

while True:
    w, h = map(int, input().split())
    if not w:
        break

    s = [list(map(int, input().split())) for _ in range(h)]
    c = list(map(int, input().split()))

    # 각 칸에 각 방향으로 도착했을 때의 최적값을 다익스트라로 구하자.
    pq = [(0, 0, 0, 0)]
    dist = [[[inf] * 4 for _ in range(w)] for _ in range(h)]
    dist[0][0][0] = 0
    while pq:
        cost, i, j, d = heappop(pq)
        if dist[i][j][d] < cost:
            continue
        for command in range(4):
            if s[i][j] == command:
                nxt_cost = cost # 명령을 따로 내릴 필요 없다.
            else:
                nxt_cost = cost + c[command] # 명령을 따로 내려야 한다.
            nxt_d = (d + command) % 4 # 다음 방향
            nxt_i = i + dir[nxt_d][0]; nxt_j = j + dir[nxt_d][1] # 다음 위치
            if 0 <= nxt_i < h and 0 <= nxt_j < w and dist[nxt_i][nxt_j][nxt_d] > nxt_cost:
                dist[nxt_i][nxt_j][nxt_d] = nxt_cost
                heappush(pq, (nxt_cost, nxt_i, nxt_j, nxt_d))

    print(min(dist[h - 1][w - 1])) # 목적지에는 어느 방향으로든 도착만 하면 된다.