[BOJ] 15906 : 변신 이동 게임

문제 : https://www.acmicpc.net/problem/15906

---

BFS DP

문제 해석

 (1,1) 에서 (r,c) 로 최대한 빠르게 이동하고 싶다. 이때, 일반상태에서는 상하좌우로 한 칸 씩만 이동이 가능하고, t 턴을 소모해 변신상태가 되면 상하좌우 중 '#' 이 있는 워프 지역으로 한 번에 이동이 가능하다.

문제 핵심

 일반 상태로도 진행할 수 있고, 변신 상태로도 탐색을 진행할 수 있으므로 현재 지점에서 일반 이동 과 변신을 시킨 후 변신 이동을 모두 진행해야한다.

알고리즘

 Dp[X][Y][S] := ( X, Y ) 지점에 상태 S로 도착하는데 필요한 최소한의 턴 수.

--> 현재 지점에서 nextX, nextY 로 이동할 때 Dp 값과 현재 시간을 비교해서 최소한의 턴 수 가 아니라면 더 탐색을 진행하지 않아도 된다.

 먼저 현재 지점에서 일반 이동을 해보고, 변신 상태가 아니라면 변신을 한 후 변신 이동을 해본다.

#include<iostream>
#include<queue>
#include<algorithm>
 
using namespace std;
 
struct box {
    int x, y, time;
    bool change;
};
 
int N, t, r, c;
int dx[4] = { -1 , 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
const int INF = 999999;
char map[501][501];
int dp[501][501][2];
queue<box> q;
 
bool check(int x, int y) {
    return (0 <= x && x < N && 0 <= y && y < N);
}
void normalMove(int curX, int curY, int curT, bool curS) {
    for (int i = 0; i < 4; i++) {
        int nextX = curX + dx[i], nextY = curY + dy[i];
        if (!check(nextX, nextY)) continue;
        if (curT + 1 < dp[nextX][nextY][curS]) {
            dp[nextX][nextY][curS] = curT + 1;
            q.push({ nextX, nextY, curT + 1, curS });
        }
    }
}
 
void specialMove(int curX, int curY, int curT, bool curS) {
    for (int i = 0; i < 4; i++) {
        int nextX = curX + dx[i], nextY = curY + dy[i];
        while (check(nextX, nextY) && map[nextX][nextY] != '#') {
            nextX += dx[i], nextY += dy[i];
        }
        if (check(nextX, nextY) && curT + 1 < dp[nextX][nextY][curS]) {
            dp[nextX][nextY][curS] = curT + 1;
            q.push({ nextX, nextY, curT + 1, curS });
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> t >> r >> c;
    r--, c--;
    for (int i = 0; i < N; i++)
        cin >> map[i];
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < 2; k++)
                dp[i][j][k] = INF;
 
    q.push({ 0, 0, 0, 0 });
    dp[0][0][0] = 0;
 
    while (!q.empty()) {
        int curX = q.front().x, curY = q.front().y;
        int curT = q.front().time;
        bool curS = q.front().change;
        q.pop();
        // 목적지 도착
        if (curX == r && curY == c) continue;
        // 그냥 이동
        normalMove(curX, curY, curT, false);
        // 변신해서 이동!
        if(curS == false) curT += t; // 변신
        specialMove(curX, curY, curT, true);
    }
    cout << min(dp[r][c][0], dp[r][c][1]) << '\n';
}

---