title: "[프로그래머스] 미로 탈출 명령어 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/150365"
description: "프로그래머스 Level 3 문제 [미로 탈출 명령어]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

def manhattan(r, c, targetr, targetc):
    return abs(r - targetr) + abs(c - targetc)

def shortest_path(r, c, targetr, targetc):
    # 사전순서에서 제일 빠르면서,
    # (r, c)에서 (targetr, targetc)에 가장 빨리 도달하는 경로를 리턴합니다.
    res = []
    if targetr - r >= 0:
        res.append('d' * (targetr - r))
    if targetc - c <= 0:
        res.append('l' * (c - targetc))
    if targetc - c > 0:
        res.append('r' * (targetc - c))
    if targetr - r < 0:
        res.append('u' * (r - targetr))
    return ''.join(res)

def solution(n, m, x, y, r, c, k):
    R, C = n, m
    startr, startc = x-1, y-1
    targetr, targetc = r-1, c-1
    
    netr, netc = targetr-startr, targetc-startc
    netd = abs(netr) + abs(netc)
    if k < netd or (k - netd) % 2 != 0:
        return 'impossible'
    
    answer = []
    r, c = startr, startc

    # 최단거리로 가면 거리가 남을때
    # 가능한 한 아래로 갑니다.
    while r < R-1 and manhattan(r, c, targetr, targetc) < k:
        r += 1
        answer.append('d'); k -= 1
    
    # 가능한 한 왼쪽으로 갑니다.
    while c > 0 and manhattan(r, c, targetr, targetc) < k:
        c -= 1
        answer.append('l'); k -= 1
    
    # 그래도 거리가 남는다는 것은 왼쪽 하단에 와있다는 겁니다.
    # 남은 거리가 남은 이동횟수와 같아질때까지 rl을 반복합니다.
    d = manhattan(r, c, targetr, targetc)
    while k > d:
        answer.append('rl'); k -= 2
    
    # 마지막으로 최단경로를 붙입니다.
    answer.append(shortest_path(r, c, targetr, targetc))

    return ''.join(answer)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges