게임 맵 최단거리 (코딩테스트, 프로그래머스, 파이썬)

문제

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

프로그래머스

 

---

풀이

큐를 사용해서 최단 경로로 도착하는 거리를 측정하였다.

재귀를 쓸 필요없이 queue는 n거리 이동시 도착 가능한 좌표들을 queue배열에 저장,

while문을 한번 할 때마다 queue 좌표들에서 인접한 maps들 중 1이 있는 것들을 queue에 저장한다.

과거의 좌표와 이동할 좌표가 공존하기 때문에 init_q 변수로 이전과 이후를 구분한다.

while문 실행시 과거 좌표까지만 for문을 돌리며 하나씩 좌표를 선택하여 인접에 1이 있으면 모아두고 

한꺼번에 queue에 더하여 추가한다.

while문 마지막에 queue = queue[init_q:]를 하여 과거 좌표를 버린다.

while문 반복 횟수가 정답이 되지만 처음 위치도 1로 취급하기 때문에 answer 초기값을 1로 설정하면 정답이다.

---

나의 코드

def solution(maps):
    answer = 1
    queue = [[0,0]]
    maps[0][0]=0
    w = len(maps[0])-1
    h = len(maps)-1
    while maps[h][w] == 1:
        init_q = len(queue)
        for i in range(init_q):
            queue += check(queue[i],maps,w,h)
        if len(queue) == init_q:
            return -1
        
        queue = queue[init_q:]
        answer += 1

    return answer

def check(target,maps,w,h):
    tmp = [[-1,0],[1,0],[0,1],[0,-1]]
    tmp_arr = []
    for i in tmp:
        y = i[0]+target[0]
        x = i[1]+target[1]
        if min(x,y)<0 or x>=len(maps[0]) or y>=len(maps):
            continue
        if maps[y][x] == 1:
            maps[y][x] = 0
            tmp_arr.append([y,x])
    return tmp_arr