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

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

코드

import queue
def solution(maps):
    cost=[[10**5]*len(maps[0]) for _ in range(len(maps))]
    cost[0][0]=1
    
    move=[[0,1],[0,-1],[1,0],[-1,0]]
    
    q=queue.Queue()
    q.put([0,0])
    
    while q.qsize():
        x,y=q.get()
        for xx,yy in move:
            nx,ny=x+xx,y+yy
            if nx in [-1,len(maps)] or ny in [-1,len(maps[0])]:
                continue
            if maps[nx][ny]==0:
                continue
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny]=cost[x][y]+1
                q.put([nx,ny])
    
    return cost[-1][-1] if cost[-1][-1]!=10**5 else -1

bfs로 풀었다.

미리 각 지점의 cost를 매우 크게 지정해두고

[0,0] 에서부터 갈 수 있으며(벽이 아닌), 이전에 방문하지 않은(cost가 적은) 곳들을 방문하면서 값을 갱신해준다.

그렇게 방문을 계속하면 답을 알 수 있다.

Discussion and feedback