[programmers] 1844. 게임맵 최단거리

문제

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

분석

이 문제는 최단거리를 구하는 문제이다! 무조건 BFS로 풀기!

• DFS/BFS 중, DFS로 풀면 Time Limit에 걸릴 수 있다. 왜냐하면 DFS 시, 이상한 루트를 잘못가게 되면 굉장히 돌아돌아돌아 가기 때문!
• 따라서 가장 가까운 edge부터 탐색하는 BFS로 문제를 풀어야한다!

1. BFS

• 이 때, 최단거리를 저장을 따로 해주지 않아도된다! 왜냐하면 BFS(너비우선탐색)으로 풀기 때문에 가장 먼저 도착한 거리가 곧 최단거리가 되기 때문이다!!!

from collections import deque
# BFS로 풀것임 -> queue 사용!
def solution(maps):
    dn_dm = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    n,m = len(maps), len(maps[0])
    visited = [[False] * m for _ in range(n)]

    shortest_path = -1
    
    queue = deque()
    queue.append((0, 0, 1))
    visited[0][0] = True

    # 만약 진영이 모두 막혀있으면, -1 바로 return
    if maps[n-1][m-1]==0:
        return -1
    if maps[n-1][m-2]==0 and maps[n-2][m-2]==0 and maps[n-2][m-1]==0:
        return -1
    
    while queue:
        cur_n, cur_m, path = queue.popleft()
        if cur_n==n-1 and cur_m==m-1:
            shortest_path = path
            break
        for i in range(4):
            next_n, next_m = cur_n + dn_dm[i][0], cur_m + dn_dm[i][1]
            
            # maps idx 안에 있어야하며
            if (next_n>=0 and next_m>=0 and next_n<n and next_m<m): 
                # 벽이 없는 자리여야하며
                if (maps[next_n][next_m] == 1):
                    # 아직 방문하지 않았어야
                    if visited[next_n][next_m] == False: 
                        visited[next_n][next_m] = True
                        queue.append((next_n, next_m, path+1))
        
    return shortest_path

문제 출력 확인

if __name__ == "__main__":
    maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
    target = 3
    
    answer = solution(maps)
    print("answer: ", answer)

answer: 11