[프로그래머스] 미로 탈출 명령어 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150365. 미로 탈출 명령어

[Lv. 3]

 

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

프로그래머스

 

풀이

우선, 'impossible'을 출력해야 하는 경우를 먼저 알아보자..

간단하게 생각해 보면, 출발지에서 도착지까지 도달할 수 있는 최소 거리를 h라 했을 때,

k = h+(0을 포함한 짝수) 여야 어떻게든 도달할 수 있다.

따라서, k보다 h가 작은 경우나, k = h + (홀수) 인 경우엔 impossible을 출력해주면 된다.

---

사전식 정렬에서 빠른 순서는, 'd', 'l', 'r', 'u' 순이다.

따라서, 목적지까지의 d/u의 최소 개수, l/r의 최소 개수를 측정하고, d가 제일 많이 오도록 하면 된다.

다만, d를 추가하는 것이 index를 초과한다면, u를 넣고 나서 d를 넣는 것이 아닌, l 또는 r을 넣어야 할 것이다. (사전순 최전방.)

---

그러므로, d와 l을 최대한 많이 넣고, 그 다음 그 수에 따라 r과 u를 넣는 식으로 진행하면 된다.

 

def solution(n, m, x, y, r, c, k):
    answer = ""

    # h = 최단거리길이
    h = abs(r-x) + abs(c-y)
    if k < h or (k-h) % 2 == 1:
        return 'impossible'

    down, left, right, up = 0, 0, 0, 0

    # d, l, r, u 최소 개수 저장
    if r-x > 0:
        down = r-x
    else:
        up = x-r

    if c-y > 0:
        right = c-y
    else:
        left = y-c

    move = k-h

    # down
    answer += "d"*down
    down = min(move//2, n-(x+down))
    answer += "d"*down
    up += down
    move -= 2*down

    # left
    answer += "l"*left
    left = min(move//2, y-left-1)
    answer += "l"*left
    right += left
    move -= 2*left

    # right, up
    answer += 'rl'*(move//2)    # 남은 movement를 rl로 대체
    answer += 'r'*right
    answer += 'u'*up

    return answer