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

접근

• DFS 또는 BFS로 풀 수 있지만 DFS로 풀었다가는 TLE에 걸릴 수 있다는 점에 명심해야 한다.

 

문제 링크

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

 

솔루션

def solution(maps):

    ROW_length = len(maps)
    COL_length = len(maps[0])
    visited = [[False for _ in range(COL_length)] for _ in range(ROW_length)]
    queue = [[0,0,1]]
    
    while queue:
        ROW, COL, DIST = queue.pop(0)
        
        # 조건에 맞지 않는 경우는 모두 추가 탐색하지 않습니다.
        if ROW < 0 or ROW > ROW_length-1 or COL < 0 or COL > COL_length-1 or \
            visited[ROW][COL] == True or maps[ROW][COL] == 0:
            continue
        
        visited[ROW][COL] = True
                
        # 만약 마지막에 도착한 경우 탐색은 종료됩니다.
        if ROW == ROW_length-1 and COL == COL_length-1:
            return DIST
        
        # 현재 위치에서 가능한 방향을 찾아 탐색 큐에 추가합니다.
        queue.append([ROW-1, COL, DIST+1])
        queue.append([ROW, COL-1, DIST+1])
        queue.append([ROW+1, COL, DIST+1])
        queue.append([ROW, COL+1, DIST+1])
    
    return -1