[BFS] 프로그래머스 level 2 게임 맵 최단거리 python 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

BFS란?

• BFS (Breadth-First Search, 너비 우선 탐색)는 그래프나 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘
• BFS는 큐를 사용하기 때문에 먼저 발견한 노드를 먼저 탐색하고, 더 멀리 있는 노드는 나중에 탐색
• 너비를 우선으로 시작 노드에서 가까운 노드부터 발견하고 탐색하기 때문에 최단 경로를 찾는 데 유용하며, 그래프의 연결 요소를 찾는 데도 적합

 

문제 접근

1. 최단 거리를 찾는 문제이므로 BFS 사용
2. 다음 이동할 좌표의 배열 값이 1이고, 배열 범위를 안 벗어나면 다음 이동 좌표 tuple을 deque에 삽입
3. 이미 한 번 지난 곳은 maps 배열에서 0으로 바꿈 이는 재 방문을 막기 위함.
4. dist라는 변수는 현재 몇 칸을 이동했는지 기록, 다음 좌표 인덱스에 현재 좌표 이동한 칸 수에 + 1을 저장
5. 현재 좌표와 목표 좌표가 같으면 dist의 목표 좌표 인덱스 값을 min 함수를 사용하여 가장 작은 값으로 대체
6. 목표에 갈 수 없으면 dist[target]= -1 이며, 갈 수 있다면 최소 거리를 리턴

 

코드

from collections import deque


def solution(maps):
    vertex = [(1, 0), (-1, 0), (0, -1), (0, 1)]
    n, m = len(maps), len(maps[0])

    # create a first in first out queue to store all the vertices for BFS
    queue: deque = deque()
    start_vertex = (0, 0)
    target = (n-1, m-1)
    maps[0][0] = 0
    
    # mark the source node as visited and enqueue it
    queue.append(start_vertex)
    
    # keep tab on distances from `start_vertex`
    dist = {start_vertex: 1, target: -1}

    while queue:
        current_vertex = queue.popleft()
        if current_vertex == target:
            dist[target] = dist[current_vertex] if dist[target] == -1 else min(dist[target], dist[current_vertex])

        # loop through all adjacent vertex
        for adjacent_vertex in vertex:
            next_y = current_vertex[0] + adjacent_vertex[0] 
            next_x = current_vertex[1] + adjacent_vertex[1] 
            
            if -1 < next_y < n and -1 < next_x < m:
                if maps[next_y][next_x] == 1:
                    maps[next_y][next_x] = 0
                    queue.append((next_y, next_x))
                    dist[(next_y, next_x)] = dist[current_vertex] + 1
    
    return dist[target]

 

 

참고 자료

https://github.com/TheAlgorithms/Python/blob/master/graphs/breadth_first_search_shortest_path_2.py