[acmicpc] 14442. 벽 부수고 이동하기 2(python)

3차원 배열을 사용 안하는 방법으로 구현하였습니다.

아래 블로그를 참고했습니다.

https://hongjw1938.tistory.com/163

import sys
from collections import deque
input=sys.stdin.readline

n,m,k=map(int,input().split())
arr=[list(map(int,input().strip())) for _ in range(n)]

dirs=[(1,0),(0,1),(-1,0),(0,-1)]
visit=[[sys.maxsize for _ in range(m)] for _ in range(n)]
q=deque()
q.append((0,0,0,1))
visit[0][0]=1
answer=-1
while q:
    r,c,cnt,move=q.popleft()
    if r==n-1 and c==m-1:
        answer=move
        break
    for i in range(4):
        nr,nc=r+dirs[i][0],c+dirs[i][1]
        if 0<=nr<n and 0<=nc<m:
        	# 부순벽의 수가 더 적은 경우 넘어감
            if visit[nr][nc]<=cnt: continue
            if arr[nr][nc]:
                if cnt<k and visit[nr][nc]>cnt+1:
                    q.append((nr, nc, cnt+1, move+1))
                    visit[nr][nc] = cnt + 1
            else:
                q.append((nr,nc,cnt,move+1))
                visit[nr][nc]=cnt

print(answer)

---

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

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