[Python] 프로그래머스 <미로 탈출 명령어>

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

프로그래머스

 

from collections import deque

def solution(n, m, x, y, r, c, k):
    answer = ''
    # 남은 거리 체크 
    def check(x1, y1):
        return abs(x1 - (r-1)) + abs(y1-(c-1))

    # k가 최단 거리보다 작거나, 필요한 거리-k가 홀수라면 도착지에 k번만에 도착 불가
    if check(x-1, y-1) > k or (check(x-1, y-1) - k) % 2:
        return 'impossible'
    # 탐색 방향 사전순으로 - d l r u
    dic = {(1,0):'d', (0,-1):'l', (0,1):'r', (-1,0):'u'}
    dq = deque()
    # 첫 좌표, 간 거리, 문자열 저장
    dq.append((x-1, y-1, 0, ''))
    while dq:
        nx, ny, cnt, route = dq.popleft()
        # 도착했는데 남은 거리가 홀수라면 도착지에 갈 수 없음
        if (nx, ny) == (r-1, c-1) and (k-cnt) % 2:
            return 'impossible'
        # k번 움직였고 도착지에 도착하면 문자열 반환
        elif (nx, ny) == (r-1, c-1) and cnt == k:
            return route
        for dx, dy in dic:
            # ni, nj는 다음 이동 좌표
            ni, nj = nx+dx, ny+dy
            if 0 <= ni < n and 0 <= nj < m:
                # 다음 이동 자리를 보는 것이므로 남은거리+지금까지의 거리+1 체크해서
                # k보다 크면 패스
                if check(ni, nj) + cnt + 1 > k:
                    continue
                dq.append((ni, nj, cnt+1, route+dic[(dx, dy)]))
                break

    # answer 사용하지 않음
    return answer