[파이썬] 백준 14948 : 군대탈출하기 (골드2)

[파이썬] 백준 14948 : 군대탈출하기 (골드)

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

---

풀이

방향성 생각

• 
  

---

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()
inside = lambda x,y: 0<=x<W and 0<=y<H

H,W = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(H)]
V = [[[float('inf')]*W for _ in range(H)] for _ in range(2)]
dire = [(1,0),(-1,0),(0,1),(0,-1)]

heap = []
hq.heappush(heap,(0,0,1,arr[0][0])) # x,y,스킬 사용 가능 횟수, 현재까지 최대 레벨
V[0][0][0] = arr[0][0]


while heap:
    x,y,skill,level = hq.heappop(heap)
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        nnx,nny = x+2*dx,y+2*dy

        # 스킬 횟수 있으면 2칸 이동 가능
        if skill:
            if inside(nnx,nny):
                nlevel = max(arr[nny][nnx],level)
                if nlevel < V[1][nny][nnx]:
                    hq.heappush(heap,(nnx,nny,0,nlevel))
                    V[1][nny][nnx] = nlevel

            # 스킬 사용 안하고 넘어가기
            if inside(nx,ny):
                nlevel = max(arr[ny][nx],level)
                if nlevel < V[0][ny][nx]:
                    hq.heappush(heap,(nx,ny,1,nlevel))
                    V[0][ny][nx] = nlevel

        # 스킬 사용 못하는 경우
        else:
            if inside(nx,ny):
                nlevel = max(arr[ny][nx],level)
                if nlevel < V[1][ny][nx]:
                    hq.heappush(heap,(nx,ny,0,nlevel))
                    V[1][ny][nx] = nlevel

print(min(V[i][-1][-1] for i in range(2)))

코멘트

• 벽뿌랑 비슷한문제