[BOJ 15906, Python 3] 변신 이동 게임

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

15906번: 변신 이동 게임

 

 

풀이

처음엔 BFS를 생각해볼 수 있는데 일반 이동은 (이동 횟수) + 1이지만, 변신모드로 변할 때는 (이동 횟수) + t가 되기 때문에 이걸 단순 큐에 넣어서 풀어보면 이미 방문한 경로가 다시 업데이트될 수도 있기 때문에 시간이 오래 걸리므로 다익스트라 알고리즘을 생각해볼 수 있습니다.

 

방문 방법은 visit 배열 2개로 나눠 각각 변신모드로 이동할 때와 일반모드로 이동할 때로 나누고, 문제 본문에서 변신 모드를 사용하여 워프로 이동할 때에는 상하좌우방향으로 각각 가까운 워프로만 이동할 수 있기 때문에 while문을 이용하여 각 방향에서 찾을 수 있는 워프를 찾아 우선순위큐에 넣어주면 됩니다.

 

 

 

거의 2.5년전에 풀다가 포기 했었는데 드디어 풀었네요

코드

from heapq import *
input = __import__('sys').stdin.readline
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
MAX = 9876543210
 
n, t, r, c = map(int, input().split())
MAP = [input() for _ in range(n)]
visit = [[[MAX]*n for _ in range(n)] for __ in range(2)]; visit[0][0][0] = 0
q = []; heappush(q, [0, 0, 0, 0])
 
while q:
    val, x, y, s = heappop(q)
    if s == 1 and visit[0][x][y] > val: visit[0][x][y] = val
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < n and visit[0][nx][ny] > val + 1:
            visit[0][nx][ny] = val + 1
            heappush(q, [val+1, nx, ny, 0])
    if s == 0 and visit[1][x][y] > val + t:
        visit[1][x][y] = val + t
        heappush(q, [val+t, x, y, 1])
    if s == 1:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            flag = False
            while 0 <= nx < n and 0 <= ny < n:
                if MAP[nx][ny] == '#': flag = True; break
                nx, ny = nx + dx[i], ny + dy[i]
            if flag and visit[1][nx][ny] > val + 1:
                visit[1][nx][ny] = val + 1
                heappush(q, [val+1, nx, ny, 1])
print(visit[0][r-1][c-1])