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

문제

---

• 미로 탈출 명령어 (LV3)

미로 탈출 명령어

n X m 미로에서 정확하게 k번 움직여서 탈출해야 하는 문제였다.
여기서 문제의 조건은 상하좌우를 각각 udlr으로 두고 이동하는 경로를 알파벳으로 나열하였을 때, 사전순으로 가장 빠른 경로를 출력하는 것이였다.

내 코드

---

처음 문제를 보고는 그래프 탐색 문제라고 생각하고 dfs를 활용하여서 문제를 풀려고 했다.
같은 격자를 두 번 이상 방문 가능하다는 조건때문에 시간 초과가 발생하였다.
그럼에도 계속해서 그래프 탐색 방식으로 문제를 해결하고 하였는데 계속 시간 초과가 발생하였다.
그래서 문제를 처음부터 다시 생각해보니 그래프 탐색없이 단순 구현으로 풀 수 있는 문제였다.
알파벳의 순서가 dlru순서이므로 가장 먼저 아래로 갈 수 있을 만큼 이동한다.
다음으로는 왼쪽으로 최대한 이동한다.
그리고는 도착지까지 이동할 만큼만 남기고 오른쪽 왼쪽을 반복하여 이동한다.(위로는 최대한 마지막에 이동해야하기 때문)
마지막으로 도착지로 이동하면 경로가 사전순으로 가장 빠른 경로가 된다.

def solution(n, m, x, y, r, c, k):
    answer = ''
    if k < abs(r - x) + abs(c - y):
        return 'impossible'
    if (k - abs(r - x) + abs(c - y)) % 2 == 1:
        return 'impossible'
    
    while k - (abs(r - x) + abs(c - y)) > 0 and x < n:
        answer += 'd'
        x += 1
        k -= 1
        
    while k - (abs(r - x) + abs(c - y)) > 0 and y > 1:
        answer += 'l'
        y -= 1
        k -= 1
    
    remain = k - (abs(r - x) + abs(c - y))
    for i in range(remain//2):
        answer += 'rl'
        k -= 2
    
    row = abs(x - r)
    col = abs(y - c)
    if x < r:
        answer += 'd' * row

    if y > c:
        answer += 'l' * col

    if y < c:
        answer += 'r' * col

    if x > r:
        answer += 'u' * row
    
    return answer

문제를 풀 때 어떤 식으로 구현할 것이고 시간복잡도가 어떻게 되는지 명확하게 계산해보고 문제를 풀어야겠다는 생각이 들었다.