[파이썬] 백준 15906 : 변신 이동 게임 (골드1)

[파이썬] 백준 15906 : 변신 이동 게임 (골드1)

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

---

풀이

방향성 생각

• 일반 grid 움직임 문제 + 상태 공간 추가이다.
• 변신모드에서는 각 방향마다 가장 가까운 워프지점이 존재하면 이동할 수 있다.
  • 변신 모드에서는 워프지점으로만 이동할 수 있다.
• 일반 모드에서는 기본 grid 탐색처럼 진행한다.
• 각 위치에서 이동할 수 있는 워프지점이 정해져있기 때문에, 미리 배열을 순회해서 이 정보를 저장해놓고 푸는 것도 좋아보인다 (맵이 커지면 중복탐색이 많이 발생할 가능성이 높다).

 

---

파이썬

import sys
import heapq as hq

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y : 0<=x<N and 0<=y<N
dires = [(1,0),(0,1),(-1,0),(0,-1)]
INF = float('inf')

N,P,ey,ex = map(int,input().split())
ey -= 1
ex -= 1

cvt = {"." : 0, "#" : 1}
arr = [list(map(cvt.get,input())) for _ in range(N)]

def di():

    # 일반 / 변신모드 힙에 넣기
    V = [[[INF]*N for _ in range(N)] for _ in range(2)]
    V[0][0][0] = 0
    V[1][0][0] = P

    heap = [(0,0,0,0),(P,0,0,1)]
    while heap:

        t,x,y,mode = hq.heappop(heap)
        nt = t+1

        # 최적 x 넘기기
        if t > V[mode][y][x]:
            continue

        # 도착
        if (x,y)==(ex,ey):
            return t

        # 변신
        if not mode and t+P < V[1][y][x]:
            V[1][y][x] = t+P
            hq.heappush(heap,(t+P,x,y,1))

        # 변신 해제
        if mode and t < V[0][y][x]:
            V[0][y][x] = t
            hq.heappush(heap,(t,x,y,0))

        # 탐색
        for dx,dy in dires:
            nx,ny = x+dx,y+dy

            if not inside(nx,ny):
                continue
            # 일반모드
            if not mode:
                if nt < V[mode][ny][nx]:
                    hq.heappush(heap,(nt,nx,ny,mode))
                    V[mode][ny][nx] = nt
            # 변신모드
            else:
                while inside(nx,ny):
                    if arr[ny][nx]:
                        if nt < V[mode][ny][nx]:
                            V[mode][ny][nx] = nt
                            hq.heappush(heap,(nt,nx,ny,1))
                        break
                    nx += dx
                    ny += dy

print(di())

---

코멘트

발문이 좀 애매...