미로의 최단거리 통로

문제 설명

7*7의 크기로 고정된 미로를 탈출하는 최단경로 길이를 구하고자 한다.

도달하지 못하면 -1, 도달하는 경우 최단거리를 반환

접근 방법

• 최단거리를 구해야하는 문제는 BFS를 활용
• 거리를 기록하며 나아가야 하기에, 거리를 기록할 dist 2차원 배열 선언
• 상 하 좌 우를 위한 dx dy 리스트 선언
• 첫 시작점을 queue에 넣고 while문 안에서 queue가 빌 때 까지(끝에 도달할 때 까지) 수행
• 탐색한 길은 다시 오지 않기 위해 1할당
• 탐색을 진행하며 길이 1씩 증가하며 dist 배열에 값 저장

작성한 코드

from collections import deque
def BFS(board):
    queue = deque()
    queue.append([0,0])
    dist = [[0] * 7 for _ in range(7)]  # 길이 저장을 위한 배열
    
    dx = [-1, 1, 0, 0]					# 상하좌우
    dy = [0, 0, -1, 1]
    answer = 0
    
    while queue:
        for _ in range(len(queue)):
            loc_x, loc_y = queue.popleft()	# 좌표 추출

            for i in range(4):
                ax = loc_x + dx[i]			# 4방향 탐색
                ay = loc_y + dy[i]

                if 0 <= ax < 7 and 0 <= ay < 7 and board[ax][ay] == 0:
                    queue.append([ax, ay])
                    board[ax][ay] = 1		# 방문 처리
                    dist[ax][ay] = answer + 1
        answer += 1

    if dist[6][6]:
        return dist[6][6]
    else:
        return -1
            
        
def solution(board):
    answer = BFS(board)
    return answer