[프로그래머스] 게임 맵 최단거리 - Python3

문제

전형적인 미로 탈출을 위한 최단거리를 구하는 문제

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

프로그래머스

• 알고리즘 분류 - 깊이/너비 우선 탐색(DFS/BFS)
• 난이도 - Level 2

---

관련 개념

최단거리를 찾는 문제의 경우, DFS보다 BFS가 효율적이다.

가령, 위 미로의 (3,3)에서 BFS로 뻗어나가면 앞으로 4번의 탐색으로 종료지점에 도달할 수 있고 그것이 최적의 해임을 보장하는 반면, DFS로 뻗어나가면 목표 지점에 도착하긴 하더라도 여러 방향으로 돌아갈 수 있기 때문에 최단거리를 보장하지 못한다.

---

접근 방법

큐로 BFS를 구현해서 풀었다.

처음엔 각 칸마다의 비용을 저장하는 이차원 배열을 따로 만들어서 더 저렴한 비용이 가능한 경우만 탐색하도록 풀었더니 정확성 테스트는 모두 통과해도 효율성 점수가 0점이 나왔다. (생각해보니까 이건 DFS에서나 필요하지 BFS는 비용 비교를 할 필요가 없었다. 각 칸의 모든 비용이 최단 거리가 되기 때문이다.)

비용 비교를 하지 않으면서 불필요하게 되돌아가는 과정을 줄이기 위해, 다른 분의 풀이를 참고하여 이미 방문했던 칸은 막아버리는 방식으로 구현했더니 풀렸다.

---

답안 코드

+5..? 9...? 까먹었다

from collections import deque

def solution(maps):
    queue = deque()
    vector = [[-1,0], [0,1], [0,-1], [1,0]]
    n,m = len(maps),len(maps[0])
    
    queue.append([0,0,1])

    while len(queue) > 0:
        r,c,cost = queue.popleft()
        
        if r == n-1 and c == m-1:
            return cost
        
        if maps[r][c] == 0:
            continue
        maps[r][c] = 0
        
        for i, j in vector:
            if 0 <= r+i < n and 0 <= c+j < m:
                if maps[r+i][c+j] == 1:
                    queue.append([r+i, c+j, cost+1])
    
            
    return -1

 

BFS가 익숙하지 않아서 DFS로 풀어보겠다고 2시간을 낑낑댄 게 좀 아깝긴 하지만 BFS 구현 방법과 장점을 확실히 알게 됐으니 나름 값진 시간이었다!