알고리즘
[프로그래머스] 게임 맵 최단거리
hminor
2023. 6. 29. 10:00
반응형
from collections import deque
# bfs와 delta 를 사용해서 풀기
# 나의 위치는 1,1 라고 하지만 배열상 (0,0)
# 상대방은 해당 배열의 가장 마지막인 (n-1, m-1)
def solution(maps):
que, mx_X_ln, mx_Y_ln = deque([[0, 0, 1]]), len(maps[0])-1, len(maps)-1 # y,x,cnt
visit = [[0]*(mx_X_ln+1) for _ in range(mx_Y_ln+1)]
while que:
y, x, cnt = que.popleft()
if visit[y][x]: continue
visit[y][x] = 1
if x == mx_X_ln and y == mx_Y_ln:
return cnt
for search in [[-1,0], [0,1], [1, 0], [0,-1]]: # delta 탐색 (위, 오른쪽, 아래, 왼쪽)
# 현재 좌표에서 델타 방향만큼 더 했을 때 maps 범위내에 있는지, 이동 좌표가 1인지, 방문하지 않았는지 체크
ny, nx = y+search[0], x+search[1]
if 0 <= nx <= mx_X_ln and 0 <= ny <= mx_Y_ln and maps[ny][nx] and not visit[ny][nx]:
que.append([ny, nx, cnt+1])
return -1