변신 이동 게임( BOJ 15906 )

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

15906번: 변신 이동 게임

 

문제 파악하기

게임 속 캐릭터를 (1, 1)에서 (r, c)까지 이동하는데 필요한 최소 턴 횟수를 구하는 문제입니다. 캐릭터는 1턴을 사용하여 상하좌우 인접한 1칸으로 움직이거나 t턴을 사용하여 변신 모드로 변신한 다음, 1턴을 사용하여 상하좌우 방향의 가장 가까운 워프 지점('#')으로 이동할 수 있습니다. 각각의 칸에서 이동할 수 있는 칸이 정해져있기에 미리 갈 수 있는 칸을 저장해놓은 다음, 캐릭터의 모드(일반 모드, 변신 모드)에 따라 목적지인 (r, c)까지 도착할 수 있는 최단 경로(턴 횟수)를 구하면 됩니다.

 

문제 해결하기

출발 지점에서 도착 지점까지의 최단 경로를 구하기 위해 사용할 수 있는 가장 빠른 알고리즘은 다익스트라 알고리즘입니다. 이번 문제 역시 다익스트라 알고리즘을 사용하면 되며, 주의할 점은 바로 모드가 2개라는 점입니다. 각각의 모드에 따라 최종 도착 시의 턴의 횟수가 달라지기 때문에 모드 별로 턴의 횟수를 기록하는 것이 필요합니다. 따라서, 거리를 저장하는 변수는 2차원 배열을 사용해서 만들어야 합니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define NMAX 505
#define INF 987654321
using namespace std;
 
struct Inp {
    int pos, cost, mod;
};
 
int N, t, r, c, ed;
char inp[NMAX][NMAX];
vector< int > graph[NMAX*NMAX][2];
 
int x, y, xx, yy;
int cpos, ccost, cmod, ncost;
int dst[NMAX*NMAX][2];
int dx[4]={-1,0,1,0}, dy[4]={0,-1,0,1};
 
struct cmp {
    bool operator()(Inp a, Inp b) { return a.cost > b.cost; }
};
priority_queue< Inp, vector< Inp >, cmp > pq;
 
bool safe(int x, int y) {
    if(x<0 or x>=N or y<0 or y>=N) return 0;
    else return 1;
}
 
int main() {
    // input
    scanf("%d %d %d %d", &N, &t, &r, &c);
    for(int i=0;i<N;i++) scanf("%s", inp[i]);
 
    // init
    ed = (r-1)*N+(c-1);
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            x = i; y = j;
 
            // 일반 모드
            for(int k=0;k<4;k++) {
                xx = x+dx[k];
                yy = y+dy[k];
 
                if(safe(xx, yy)) graph[x*N+y][0].push_back(xx*N+yy);
            }
 
            // 변신 모드
            for(int k=0;k<4;k++) {
                xx = x; yy = y;
                while(safe(xx, yy)) {
                    xx += dx[k];
                    yy += dy[k];
 
                    if(inp[xx][yy] == '#') {
                        graph[x*N+y][1].push_back(xx*N+yy);
                        break;
                    }
                }
            }
 
        }
    }
 
    // 다익스트라 알고리즘
    for(int i=0;i<N*N;i++) dst[i][0] = dst[i][1] = INF;
 
    dst[0][0] = 0;
    pq.push({0, 0, 0});
 
    while(!pq.empty()) {
        cpos = pq.top().pos;
        ccost = pq.top().cost;
        cmod = pq.top().mod;
        pq.pop();
 
        if(cpos == ed) break;
 
        for(int k=0;k<2;k++) {
            for(int npos:graph[cpos][k]) {
                // 일반 이동
                if(k == 0) ncost = ccost + 1;
                else {
                    // 특별 이동
                    if(cmod == 0) ncost = ccost + t + 1;
                    else ncost = ccost + 1;
                }
 
                if(ncost < dst[npos][k]) {
                    dst[npos][k] = ncost;
                    pq.push({npos, ncost, k});
                }
            }
        }
    }
 
    printf("%d", min( dst[ed][0], dst[ed][1] ));
 
}

후기

기본적인 다익스트라 알고리즘이지만 문제 속에 살짝 숨어있기에 재미있게 해결한 문제입니다. 최단 경로 알고리즘을 배운 사람에게 추천하고 싶은 활용 문제입니다.