[파이썬] 5105. 미로의 거리

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

NxN 크기의 미로에서 출발지 목적지가 주어진다.

이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오.

경로가 있는 경우 출발에서 도착까지 가는데 지나야 하는 최소한의 칸 수를, 경로가 없는 경우 0을 출력한다.

다음은 5x5 미로의 예이다. 1은 벽, 0은 통로를 나타내며 미로 밖으로 벗어나서는 안된다.

13101
10101
10101
10101
10021

마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 5개의 칸을 지나 도착할 수 있다.


[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50

다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 5<=N<=100

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

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

입력	출력
3 5 13101 10101 10101 10101 10021 5 10031 10111 10101 10101 12001 5 00013 01110 21000 01111 00000	#1 5 #2 5 #3 0

 

🎀 다른사람 풀이

 

def IsSafe(y, x) :			# 미로 좌표 검사
    return 0 <= y < N and 0 <= x < N and (Maze[y][x] == 0 or Maze[y][x] == 3)

def BFS(start_y, start_x):
    global D_result
    Q.append((start_y, start_x))
    visited.append((start_y, start_x))		# 방문처리

    while Q :
        start_y, start_x=Q.pop(0)
        for dir in range(4) :			# 상하좌우 탐색
            NewY=start_y+dy[dir]
            NewX=start_x+dx[dir]
            if IsSafe(NewY, NewX) and (NewY, NewX) not in visited :
                Q.append((NewY, NewX))
                visited.append((NewY, NewX))
                Distance[NewY][NewX]=Distance[start_y][start_x]+1
                if Maze[NewY][NewX] == 3 :		# 도착하면
                    D_result=Distance[NewY][NewX]-1

TC = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for tc in range(1, TC + 1):
    N = int(input())		# 미로의 크기
    Maze = [list(map(int, input())) for _ in range(N)]  # 1:벽 0: 통로 3: 도착 2: 출발
    visited = [[0] * N for _ in range(N)]

    for y in range(N) :  # 시작점 찾기
        for x in range(N) :
            if Maze[y][x] == 2 :
                start_y, start_x = y, x

    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]

    D_result = 0
    Q=[]
    Distance=[[0]*N for _ in range(N)]			# 거리
    BFS(start_y, start_x)
    print(f"#{tc} {D_result}")

 

출발점 좌표를 구하고 BFS함수에 파라미터 값으로 넣고 호출한다.

방문 리스트 visited를 만들고 방문할 때마다 방문한 좌표를 담는다.

리스트 Q에 값이 있을 동안에 반복한다.

Q에서 뺀 값을 변수에 담고 상하좌우를 탐색한다. 좌표가 미로의 범위내에 있고 벽이 아니고 방문하지 않았다면 Q와 visited에 담는다. 탐색한 위치의 Distance에 기준점 Distance 값+1을 할당한다.

Maze[NewY][NewX]가 3이면 도착이다. 도착은 포함안하므로 1 뺀 값을 D_result에 할당한다.

다른 풀이도 더 찾아봤지만 위와 비슷함.