Written by
최태열
on
on
[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