BOJ 5120 - Martian Pits 링크
(2024.04.01 기준 G1)

문제

$h \times w$ 크기의 지도가 주어진다. 각 칸은 $4$개의 문자 중 하나이다.

• .: 빈 공간
• P: 구덩이
• R: 시작 위치
• D: 목적지

시작할 때엔 위쪽을 바라보고 있으며 속도는 $0$ $cm/s$이다. 매 초 다음과 같은 행동을 할 수 있다.

• 전진: 바라보는 방향으로 $1$ $cm/s$ 속도로 출발한다.
• 후진: 바라보는 방향 반대로 $1$ $cm/s$ 속도로 출발한다.
• 빠르게: 현재 속도보다 $1$ $cm/s$ 더 빠르게 해서 출발한다. 단, $5$ $cm/s$보다 빨라질 수 없다.
• 느리게: 현재 속도보다 $1$ $cm/s$ 더 느리게 해서 출발한다.
• 정지: 현재 칸에서 멈춘다.
• 오른쪽으로: 바라보는 방향을 현재 방향의 오른쪽으로 $90$도 회전한다.
• 왼쪽으로: 바라보는 방향을 현재 방향의 왼쪽으로 $90$도 회전한다.
• 유지: 현재 속도와 방향을 유지한다.

'전진', '후진, '오른쪽으로', '왼쪽으로'는 멈춘 상태일 때만 가능하다.

위와 같은 행동을 적절히 이용해서 목적지에 멈춘 상태가 되는 최단 시간 출력

알고리즘

구현이 많은 BFS 문제

풀이

문제에서의 요소는 위치, 바라보는 방향, 속도, 전진? 후진?으로 총 네 가지이다.

위쪽을 바라보고 앞으로 전진, 아래쪽을 바라보고 뒤쪽으로 전진. 이 두 경우는 같은 경우이다. 그러므로 방향은 상하, 좌우 총 두 가지로 잡고, 속도는 $[-5, 5]$ 구간으로 잡으면 된다. 그러면 이제 총 요소는 세 가지가 된다.

매 초 움직이면서 도착지까지의 최단 거리를 묻는 문제이므로 BFS를 사용해야 함을 알 수 있다. 도착지의 좌표는 $(ei, ej)$로 나타내며, $d$는 방향이 상하일 때 $0$, 좌우일 때 $1$. $s$는 $-5$ 이상 $5$ 이하의 속도를 나타내는 변수라고 생각하자.
$dist(i, j, d, s)$를 $i$번째 줄 $j$번째 칸 위치에 방향 $d$, 속도 $s$인 상태로 도착할 때의 최단 거리라고 정의하면, 우리는 $dist(ei, ej, 0, 0)$과 $dist(ei, ej, 1, 0)$을 구하면 되는 것이다.

이제 매 초 할 수 있는 행동 중 하나를 하면서 BFS를 진행하면 된다. 이동하는 루트에 구덩이가 있는지 확인만 잘하면 어렵지 않게 AC를 받을 수 있다.

코드

• C++

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

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

const pii dir[2] = {{1, 0}, {0, 1}};

void solve(){
    int h, w; cin >> h >> w;
    string matrix[h]; for (int i = 0; i < h; i++) cin >> matrix[i];

    // dist(i, j, d, s): i번째 줄 j번째 칸 위치에 방향 d, 속도 s인 상태로 도착할 때의 최단 거리
    // d는 방향이 상하일 때 0, 좌우일 때 1. s는 -5 이상 5 이하의 속도.
    // 속도는 -5부터 시작이므로 5를 더해준다.
    queue<tiiii> q;
    int dist[h][w][2][11], ei, ej; memset(dist, -1, sizeof(dist));
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
        if (matrix[i][j] == 'R'){
            q.push({i, j, 0, 0});
            dist[i][j][0][5] = 0;
        }
        else if (matrix[i][j] == 'D'){
            ei = i; ej = j; // 도착지 좌표
        }
    }

    while (!q.empty()){
        auto [i, j, d, s] = q.front(); q.pop();

        // 회전은 멈춰있는 상태에서만 가능하다.
        if (s == 0) if (!(~dist[i][j][d ^ 1][s + 5])){
            q.push({i, j, d ^ 1, s});
            dist[i][j][d ^ 1][s + 5] = dist[i][j][d][s + 5] + 1;
        }

        // 가능한 속도는 s-1, s, s+1, 0이다.
        for (int s_: {s - 1, s, s + 1, 0}){

            // 속도가 -5 이상 5 이하인지 확인한다.
            if (!(-5 <= s_ && s_ <= 5)) continue;

            // s_ 속도로 1초 후에 도착하는 좌표를 구한다.
            int ni = i + dir[d].first * s_, nj = j + dir[d].second * s_;

            // 현재 좌표에서 도착하는 좌표까지의 루트가 유효한지 검사한다.
            auto [di, dj] = dir[d]; // 방향
            if (s_ < 0) di *= -1, dj *= -1;
            int ii = i, jj = j;
            bool is_valid = true;
            while (true){
                if (!(0 <= ii && ii < h && 0 <= jj && jj < w)){ // 범위를 벗어나는 좌표인가?
                    is_valid = false;
                    break;
                }
                if (matrix[ii][jj] == 'P'){ // 구덩이가 있는 좌표인가?
                    is_valid = false;
                    break;
                }
                if (ii == ni && jj == nj) // 도착하는 좌표까지 검사했으면 종료
                    break;
                ii += di; jj += dj;
            }
            if (!is_valid) continue;

            //  도착하는 좌표에 동일한 방향과 속도로 도착한 적이 있는지 검사
            if (!(~dist[ni][nj][d][s_ + 5])){
                q.push({ni, nj, d, s_});
                dist[ni][nj][d][s_ + 5] = dist[i][j][d][s + 5] + 1;
            }
        }
    }

    // 도착지에 속도 0인 최단 거리가 있는지 확인 및 출력
    // 방향은 상관없다.
    if (~dist[ei][ej][0][5]){
        if (~dist[ei][ej][1][5]) cout << min(dist[ei][ej][0][5], dist[ei][ej][1][5]) << '\n';
        else cout << dist[ei][ej][0][5] << '\n';
    }
    else{
        if (~dist[ei][ej][1][5]) cout << dist[ei][ej][1][5] << '\n';
        else cout << "Impossible\n";
    }
}

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

    int T; cin >> T;
    for (int x = 1; x <= T; x++){
        cout << "Data Set " << x << ":\n";
        solve();
        cout << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline
from collections import deque

dir = [(1, 0), (0, 1)]

def solve():
    h, w = map(int, input().split())
    matrix = [input().strip() for _ in range(h)]

    # dist(i, j, d, s): i번째 줄 j번째 칸 위치에 방향 d, 속도 s인 상태로 도착할 때의 최단 거리
    # d는 방향이 상하일 때 0, 좌우일 때 1. s는 -5 이상 5 이하의 속도.
    # 속도는 -5부터 시작이므로 5를 더해준다.
    dq = deque()
    dist = [[[[-1] * 11 for _ in range(2)] for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == 'R':
                dq.append((i, j, 0, 0))
                dist[i][j][0][5] = 0
            elif matrix[i][j] == 'D':
                ei = i; ej = j # 도착지 좌표

    while dq:
        i, j, d, s = dq.popleft()

        # 회전은 멈춰있는 상태에서만 가능하다.
        if s == 0:
            if not ~dist[i][j][d ^ 1][s + 5]:
                dq.append((i, j, d ^ 1, s))
                dist[i][j][d ^ 1][s + 5] = dist[i][j][d][s + 5] + 1

        # 가능한 속도는 s-1, s, s+1, 0이다.
        for s_ in [s - 1, s, s + 1, 0]:

            # 속도가 -5 이상 5 이하인지 확인한다.
            if not (-5 <= s_ <= 5):
                continue

            # s_ 속도로 1초 후에 도착하는 좌표를 구한다.
            ni = i + dir[d][0] * s_; nj = j + dir[d][1] * s_

            # 현재 좌표에서 도착하는 좌표까지의 루트가 유효한지 검사한다.
            di, dj = dir[d] # 방향
            if s_ < 0:
                di *= -1; dj *= -1
            ii = i; jj = j
            is_valid = True
            while True:
                if not (0 <= ii < h and 0 <= jj < w): # 범위를 벗어나는 좌표인가?
                    is_valid = False
                    break
                if matrix[ii][jj] == 'P': # 구덩이가 있는 좌표인가?
                    is_valid = False
                    break
                if ii == ni and jj == nj: # 도착하는 좌표까지 검사했으면 종료
                    break
                ii += di; jj += dj
            if not is_valid:
                continue

            # 도착하는 좌표에 동일한 방향과 속도로 도착한 적이 있는지 검사
            if not ~dist[ni][nj][d][s_ + 5]:
                dq.append((ni, nj, d, s_))
                dist[ni][nj][d][s_ + 5] = dist[i][j][d][s + 5] + 1

    # 도착지에 속도 0인 최단 거리가 있는지 확인 및 출력
    # 방향은 상관없다.
    if ~dist[ei][ej][0][5]:
        if ~dist[ei][ej][1][5]:
            print(min(dist[ei][ej][0][5], dist[ei][ej][1][5]))
        else:
            print(dist[ei][ej][0][5])
    else:
        if ~dist[ei][ej][1][5]:
            print(dist[ei][ej][1][5])
        else:
            print('Impossible')

for x in range(1, int(input()) + 1):
    print('Data Set %d:' % x)
    solve()
    print()