[프로그래머스 / 파이썬] 2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어

프로그래머스에 존재하는 연습 문제이다.

 

문제 링크

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

프로그래머스

---

문제 해석

미로크기 n, m 시작 좌표 x, y 목적 좌표 r, c 이동 거리 k가 주어진다.

이동 방향은 상하좌우 4방향이며, 이동하는 경우 각각 u, d, l, r 명령어를 사용하게 된다.

시작 좌표로부터 도착 좌표까지 주어진 k의 이동거리는 일치해야 한다.

이때 이동하는 명령어가 사전순으로 가장 빠른 명령어가 될 경우를 반환하는 문제이다.

---

문제 풀이

백준에서 비슷한 문제를 푼 기억이 있어서 bfs를 통해 짝수, 홀수를 나누어 풀려고 했다.

하지만 이는 완전히 틀린 접근법이였다.

 

이 문제는 그리디하게 풀 수 있다. 사전순으로 가장 빠른 명령어가 되려면 d l r u 순으로 명령어를 사용해야 한다.

따라서 앞서서 최대한 d를 많이 사용하고, l을 많이 사용해야 한다. 이후 ru를 반복해서 사용하는 것이 가장 빠른 명령어가 된다.

ex) "dddddllllrlrlrl"

즉 위 로직을 통해 이동 거리를 계산하고, 매번 현재 좌표에서 도착 좌표까지의 거리를 계산한다. 현재 좌표에서 도착 좌표까지의 거리와 이동할 거리가 남아있다면 위 로직을 계속 반복한다.

이후 (현재 좌표에서 도착 좌표까지의 거리 == 남은 이동거리)가 일치하는 경우 해당 좌표로부터 도착 지점까지 d l r u 순으로 이동하면

답을 구할 수 있다.

 

추가적으로 시작 좌표부터 도착 좌표까지의 거리와 k가 모두 동일한 홀수나 짝수여야 이동 좌표로 도착할 수 있다.

---

문제 코드

# 이동 순서: ['d', 'l', 'r', 'u']

# 남은 거리 계산 함수
def calc_dist(x, y, r, c):
    return abs(x - r) + abs(y - c)

def solution(n, m, x, y, r, c, k):
    if (k - calc_dist(x, y, r, c)) % 2 or k < calc_dist(x, y, r, c):
        return "impossible"
    answer = ""
    move = 0
    # 아래로 최대한 이동
    while x < n and (k - move) > calc_dist(x, y, r, c):
        move += 1
        x += 1
        answer += "d"
    # 좌측으로 최대한 이동
    while 1 < y and (k - move) > calc_dist(x, y, r, c):
        move += 1
        y -= 1
        answer += "l"
        
    # 우좌 반복 이동
    while (k - move) > calc_dist(x, y, r, c):
        move += 2
        answer += "rl"
    
    # 가야할 길로 이동 dlru 순으로 이동
    if x < r:
        answer += "d" * (r - x)
        x = r
    if y > c:
        answer += "l" * (y - c)
        y = c
    if y < c:
        answer += "r" * (c - y)
        y = c
    if x > r:
        answer += "u" * (x - r)
        x = r
    return answer