[백준 / BOJ] 15906 변신 이동 게임

문제

출처 : www.acmicpc.net/problem/15906

15906번: 변신 이동 게임

성호는 새로운 모바일 게임을 다운로드 했다.

성호의 캐릭터는 N*N의 위치에서 상,하,좌,우로 1칸 움직일수있는데, 이때, 캐릭터가 변신모드라면, 상,하,좌,우중 가장 가까운 워프지점으로만 갈수있다. (변신모드로 전환하는데는 t만큼의 턴이 소요된다.) 성호의 캐릭터가 목표지점까지 도달하는데 걸리는 최소한의 턴을 구하는문제다.

 

풀이

다익스트라로 풀리는 문제였다.

 

(a,b)에 도달했을때의 최소시간을 변신하고 온시간, 변신하지않고 온시간으로 나눠서 구해줘야 하므로 3차원 배열을 만들고, (a,b)에 도달했을때의 시간이 미리 저장되어있는 시간보다 크다면, 해당 방향으로는 더이상 탐색해주지 않았다.

 

매 이동마다, 변신을 하고 이동한경우 와 변신을 하지않고 이동한 경우를 봐줬다.

예를들어, 지금이 변신하지 않은 모드라면, 현재위치에 변신 모드를 하나 만들어놓고, 상하좌우로 움직여준다.

(Y좌표, X좌표, 모드(1 = 변신, 0 = 일반))

(1,1,0)이라면,

(1,1,1)을 만들어놓고, (1,2,0) (2,1,0) (0,1,0) (1,0,0) 4방향으로 움직여줌

변신했을경우또한 이처럼 만들고, 최종목적지에 도달했을때, 최소시간을 출력해주면 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/15906%20%EB%B3%80%EC%8B%A0%20%EC%9D%B4%EB%8F%99%20%EA%B2%8C%EC%9E%84/main.cpp

devxb/JJUNalgo