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

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

접근법

DFS의 경우 최단거리의 길을 찾음과 동시에 종료하는 것이 아니라 모든 경우를 순회하여 Maximum Recursion Error을 일으킨다.
BFS의 경우 움직임을 1칸씩 늘려가며 순차적인 순회가 가능하기 때문에 최단거리를 찾음과 동시에 종료시킬 수 있다.

필자는 큐에서 꺼낼 때 방문처리를 했는데 이는 만약 다음 방문할 블록들을 큐에 넣을 때 큐에 들어있는 블록이라도 아직 꺼내지 않았다면 방문하지 않았다고 생각하고 재삽입을 할 것이므로 같은 블록이 여러번 들어가는 상황이 생긴다.

• 꼭 방문처리는 큐에 삽입하기 이전에 해야한다!

코드

def solution(maps):
    n = len(maps)-1
    m = len(maps[0])-1
    # BFS
    q = []
    # 시작점
    maps[0][0] = 0
    q.append( (0,0,1) )
    while( q ):
        cur = q.pop(0)
        row_i,col_i,count = cur[0],cur[1],cur[2]
        # 종료조건
        if( row_i == n and col_i == m ):
            return count
        # 큐에 넣을때 방문처리를 함 -> 중복으로 같은 블록을 큐에 넣는 경우 방지
        if( col_i > 0 and maps[row_i][col_i-1] ):
            maps[row_i][col_i-1] = 0 
            q.append( (row_i,col_i-1,count+1) )
        if( col_i < m and maps[row_i][col_i+1] ):
            maps[row_i][col_i+1] = 0
            q.append( (row_i,col_i+1,count+1) )
        if( row_i > 0 and maps[row_i-1][col_i] ):
            maps[row_i-1][col_i] = 0
            q.append( (row_i-1,col_i,count+1) )
        if( row_i < n and maps[row_i+1][col_i] ):
            maps[row_i+1][col_i] = 0
            q.append( (row_i+1,col_i,count+1) )
    # 못찾은 경우
    return -1