BFS를 이용한 미로 탈출

from collections import deque

T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    maze=[list(map(int,input())) for _ in range(N)]
    ds=[[1,-1,0,0],[0,0,1,-1]]
    goal=0

    for i in range(N):
        for j in range(N):
            if maze[i][j] == 3:
                x, y = j, i
                break

    queue=deque([])
    queue.append([x,y,0])

    while maze[y][x] != 2:
        a = queue.popleft()
        xx, yy = a[0], a[1]
        cnt = a[2]
        maze[yy][xx]=1

        for _ in range(4):
            dx = xx+ds[0][_]
            dy = yy+ds[1][_]
            if 0<=dx<N and 0<=dy<N and maze[dy][dx]==0:
                dcnt=cnt+1
                queue.append([dx,dy,dcnt])
            elif 0<=dx<N and 0<=dy<N and maze[dy][dx]==2:
                goal=cnt
                x=dx
                y=dy
                break
        
        if not queue:
            break
        
    print(f'#{test_case} {goal}')