[SWEA] 미로의 거리

NXN 크기의 미로에서 출발지와 목적지가 주어지고, 최소 몇 개의 칸을 지나야 출발지에서 도착지에 다다를 수 있는지 알아보는 프로그램을 코딩하는 문제이다.

​

입력은 0 : 통로, 1:벽, 2:출발, 3:도착 이다.

distance 리스트를 만들어서 따로 거리 정보를 저장한다.

 

from collections import deque

test_case = int(input())
pos= [(1, 0), (0, 1), (-1, 0), (0, -1)]

def check(y, x): # 갈 수 있는 곳인지 체크
    return 0<=x<n and 0<=y<n and (maps[y][x] == 0 or maps[y][x] == 3)

def bfs(y, x): # bfs
    queue = deque([(y,x)])
    visited = deque()

    while queue:
        sy, sx = queue.popleft()
        visited.append((sy, sx))

        for d1, d2 in pos:
            ny = sy + d1
            nx = sx + d2

            if check(ny, nx) and ((ny, nx) not in visited): # 이동할 수 있는지, 방문한 곳인지 체크
                queue.append((ny, nx))
                distance[ny][nx] = distance[sy][sx] + 1 #거리 저장

                if maps[ny][nx] == 3 :
                    answer = distance[ny][nx] - 1
                    return answer
    return 0

for test in range(test_case):
    n = int(input())

    maps = [list(map(int, list(input()))) for _ in range(n)]
    distance = [[0]*n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if maps[i][j] == 2 :
                print('#{} {}'.format(test+1, bfs(i,j)))
                break