[파이썬] 백준 14442 : 벽 부수고 이동하기 2 (골드3)

[파이썬] 백준 14442 : 벽 부수고 이동하기 2 (골드3)

14442번: 벽 부수고 이동하기 2

---

문제

---

풀이

방향성 생각

간단한 최단거리 문제. 다익처럼 최단거리 갱신하는 경우에만 큐에 넣어서 시간 줄여주기

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w,skill = map(int,input().split())
arr = [list(input()) for _ in range(h)]

inf = 1e9
visit = [[[inf]*w for _ in range(h)] for _ in range(skill+1)]

dire = [(1,0),(0,1),(-1,0),(0,-1)]
visit[0][0][0] = 1
q = deque([(0,0,0,1)])
while q:
    x,y,s,t = q.popleft()
    for dx,dy in dire:
        nx,ny,ns,nt = x+dx,y+dy,s+1,t+1

        if 0<=nx<w and 0<=ny<h:
            if arr[ny][nx] == '0' and nt < visit[s][ny][nx]:
                visit[s][ny][nx] = nt
                q.append((nx,ny,s,nt))
            elif arr[ny][nx] == '1' and s < skill and nt < visit[ns][ny][nx]:
                visit[ns][ny][nx] = nt
                q.append((nx,ny,ns,nt))

answer = min(visit[i][-1][-1] for i in range(skill+1))
print(-1) if answer == inf else print(answer)

 

코멘트