Queue - 미로의 거리

기존의 미로 문제에서 각 경우의 count(지나온 칸의 수)를 저장해줄 리스트(save)가 추가된다.

• 이동한 거리를 세는 것이므로 도착점을 제외해야한다. 구한 값에서 -1을 해 준다.

from collections import deque
move=[(-1,0),(1,0),(0,1),(0,-1)]#위 아래 오른 왼

for tc in range(1, int(input())+1):
    N= int(input())
    arr=[list(map(int,input())) for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if arr[i][j]==2:
                start,end=i,j
    
    chk=deque()
    chk.append((start,end))
    save=[[0]*N for _ in range(N)]
    cnt=0
    
    while chk:
        x,y=chk.popleft()
        if arr[x][y]==3:
            cnt=save[x][y]-1
            break
        arr[x][y]=1
        
        for i in range(4):
            mx=x+move[i][0]
            my=y+move[i][1]
            
            if 0<=mx<N and 0<=my<N and arr[mx][my]!=1:
                chk.append((mx,my))
                save[mx][my]=save[x][y]+1

    print(f'#{tc} {cnt}')