[백준/15906] 변신 이동 게임 (Python)

Problem : https://www.acmicpc.net/problem/15906

15906번: 변신 이동 게임

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:34:49

 

---

 

문제 설명

 

 

성호는 새로운 모바일 게임을 다운로드했다. 이 게임은 NxN 크기의 2차원 격자의 시작 지점에 있는 캐릭터를 조작해서 목표 지점까지 이동시키면 클리어되는 게임이다. 캐릭터의 상태는 일반 모드와 변신 모드, 2 가지다. 일반 모드일 때 캐릭터는 한 턴에 상하좌우 중에서 한 방향으로 한 칸 움직일 수가 있지만, 변신 모드라면 움직이는 방식이 달라진다. 

격자의 일부 칸에는 워프 지점이 있을 수가 있는데, 캐릭터가 변신 모드라면 한 턴에 캐릭터의 현재 칸을 기준으로 상하좌우 중 한 방향에 있는 가장 가까운 워프 지점으로 이동할 수만 있다. 만약 특정 방향에 워프 지점이 존재하지 않는다면 그 방향으로는 움직일 수 없다. 

일반 모드에서 변신 모드가 되는 데에는 t개의 턴이 소모되며, 변신 모드에서 일반 모드로 돌아가는 데에는 턴이 소모되지 않는다. 성호는 요즘 너무 바빠서 게임을 빨리 클리어하고 삭제해버리고 싶었다. 캐릭터가 최초에 1행 1열에 존재하며, 일반 모드인 상태일 때, 성호를 대신하여 게임을 클리어하는 데 필요한 최소 턴 수를 구해주자.

 

 

입력 및 출력

 

입력

 

첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다.

다음 줄에 2차원 격자의 워프 지점 정보가 N개의 줄에 걸쳐 주어진다. 각 줄은 N개의 문자로 이루어져 있으며, 각 문자는 '#' 이거나 '.' 이다. '#'는 워프 지점이 있는 칸을 나타내며, '.'는 워프 지점이 없는 평범한 칸을 나타낸다.

 

출력

 

게임을 클리어하는 데에 필요한 최소 턴 수를 출력한다.

 

입력 예시

 

3 1 1 3
.#.
...
...

 

출력 예시

 

2

 

 

---

 

풀이

 

BFS, 혹은 이동 시간을 가중치로 한 우선순위 큐(이 때는 다익스트라에 가깝다)로 풀이해 볼 수 있다.

 

주의할 점 : visited 배열을 선언할 때, 맵 좌표 및 변신 상태를 저장하는 3차원 배열을 선언해야 한다.

 

#....# 구조에서 가장 왼쪽에 위치하였고 가장 오른쪽이 목적지인 경우를 고려해 보자. 일반 모드일 때 t = 5, 변신 모드일 때 t = 8, 변신 비용 T = 10이라고 두자. 최적해는 변신 상태일 때 1번의 이동을 하는 t = 9이지만, visited 배열에서 이를 고려하지 않으면 삽입 순서에 따라 일반 모드일 때만 고려하게 되는 불상사가 벌어질 수 있다. 즉 이 때는 t = 10라는 오답을 내게 된다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
MAX = float('inf')
N, T, R, C = map(int, input().split())
R -= 1
C -= 1
map_list = [input().strip() for _ in range(N)]
visited = [[[MAX]*2 for _ in range(N)] for _ in range(N)]
visited[0][0][0] = 0
q = deque([(0, 0, 0, 0)])

def warp(r, c, k) :
  r, c = r + dr[k], c + dc[k]
  while -1 < r < N and -1 < c < N :
    if map_list[r][c] == "#" :
      return (r, c)
    r += dr[k]
    c += dc[k]
  return (MAX, MAX)

while q :
  r, c, t, w = q.popleft()
  if (r, c) == (R, C) :
    continue
  for k in range(4) :
    ar, ac = r + dr[k], c + dc[k]
    if -1 < ar < N and -1 < ac < N and visited[ar][ac][0] > t + 1 :
      visited[ar][ac][0] = t + 1
      q.append((ar, ac, t+1, 0))
    wr, wc = warp(r, c, k)
    at = t + 1 if w else t + 1 + T
    if wr < MAX and visited[wr][wc][1] > at :
      visited[wr][wc][1] = at
      q.append((wr, wc, at, 1))

print(min(visited[R][C]))

풀이 완료!