[파이썬] 게임 맵 최단거리 [CODING TEST #51]

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

 

 

(0,0)에서 (n-1,m-1) 까지의 최소 거리를 반환하거나 도달하지 못하면 -1을 return

BFS로 간단하게 풀 수 있었다.

그런데 효율성 테스트에서 계속 실패했는데,

한 번 방문한 곳을 다시 방문하지 못하게 하기 위해 visited = True를 큐에서 뺄 때가 아니라, 넣을 때 해야 한다.

큐에서 뺄 때 방문 체크를 하면 BFS 특성 상 하나의 노드가 여러번 돌아갈 수 있기 때문이다.

프로그래머스 질문 탭에서 발견한 너무나도 좋은 내용이었다. 감사합니다.

 

from collections import deque
def solution(maps):
    INF = 987654321
    answer = 0
    visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    dist = [[INF for _ in range(len(maps[0]))] for _ in range(len(maps))]
    q = deque()
    q.append((0,0))
    
    moves = [[1,0],[0,1],[-1,0],[0,-1]]
    dist[0][0] = 1
    while q:
        x, y = q.popleft()     
#       visited[dy][dx] = True
        for move in moves:
            dx = x + move[0]
            dy = y + move[1]
            # 길이면 push.
            if 0 <= dx < len(maps[0]) and 0 <= dy < len(maps) and maps[dy][dx] == 1 and visited[dy][dx] == False:
                q.append((dx,dy))
                visited[dy][dx] = True
                # 해당 경로가 더 짧으면 갱신, 길면 pass
                if dist[dy][dx] > dist[y][x] + 1:
                    dist[dy][dx] = dist[y][x] + 1
                
    if dist[-1][-1] == INF:
        return -1
    else:
        return dist[-1][-1]