6일차 - 미로의 거리

from collections import deque
delta = [[0,1], [0,-1], [1,0], [-1,0]]

for t in range(int(input())):
    n = int(input())
    maze = [list(map(int, input().rstrip())) for _ in range(n)]

    dept_point = tuple()
    objt_point = tuple()

    for i in range(n):
        for j in range(n):
            if maze[i][j] == 2:
                dept_point = (i, j)
            elif maze[i][j] == 3:
                objt_point = (i, j)

    q = deque([dept_point])
    predecessor = [[0] * n for _ in range(n)]

    while q:
        k = q.pop()
        maze[k[0]][k[1]] = 9

        for dx, dy in delta:
            r = k[0] + dx
            c = k[1] + dy

            if 0 <= r < n and 0 <= c < n and (maze[r][c] == 0 or maze[r][c] == 3):
                q.appendleft((r,c))
                maze[r][c] = 9
                predecessor[r][c] = predecessor[k[0]][k[1]] + 1

    if predecessor[objt_point[0]][objt_point[1]] == 0:
        print(f"#{t+1} 0")
    else:
        print(f"#{t+1} {predecessor[objt_point[0]][objt_point[1]] - 1}")

 

간단한 BFS 최단거리 문제이다! 옛날에 했던 코드 보면서 다시 BFS 감을 깨우치고 작성햇다

간단하게 갔다온 곳 표시해주고 predecessor에 거리 저장해주면 되는 문제이다~