[Programmers] Lv2. 게임 맵 최단거리

문제

바로가기

코딩테스트 연습 - 게임 맵 최단거리

 

풀이

bfs를 사용해서 최단 거리를 구하고, visit을 확인하면서 갔던 경로는 가지 않도록 함

 

코드

from collections import deque

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def solution(maps):
    n, m = len(maps) - 1, len(maps[0]) - 1
    Q = deque([(0, 0, 1)])
    visit = set([(0, 0)])
    while Q:
        r, c, dis = Q.popleft()
        for i in range(4):
            nr, nc = r + d[i][0], c + d[i][1]
            if 0 <= nr <= n and 0 <= nc <= m and maps[nr][nc] == 1:
                if nr == n and nc == m:
                    return dis + 1
                if (nr, nc) in visit:
                    continue
                visit.add((nr, nc))
                Q.append((nr, nc, dis + 1))
    return -1