[프로그래머스][Python] 2023 KAKAO BLIND RECRUITMENT : 미로 탈출 명령어

📚 문제

---

Lv 3

• 사전 순으로 가장 빠른 경로를 찾고 있다는 뜻은 이동 순서에 우선순위가 있다는 뜻이다.
  • d l r u 순으로 우선순위를 가진다.
  • dfs 에서는 Stack 에 가장 마지막에 넣는 것이 가장 높은 우선순위를 가진다.
• dfs 도중에 남은 움직임으로 도착지에 도착할 수 없는 경우는 도중 삭제한다.

💡 풀이과정

---

1. d - l - r - u 순으로 우선순위를 가지기에 이를 반대 배열로 만든다.
2. stack 에 반대 배열을 순회하며 u - r - l - d 순으로 push 되도록 한다.
3. dfs 중 도착지 거리를 계산해 거리가 남은 이동보다 크다면 continue 한다.

💻 코드

---

def solution(n, m, x, y, r, c, k):
    dx = [-1, 0, 0, 1]
    dy = [0, 1, -1, 0]
    dpath = ['u', 'r', 'l', 'd']

    def get_dist(x1, y1, x2, y2):
        return abs(x1 - x2) + abs(y1 - y2)

    def dfs():
        stack = []
        stack.append([x, y, 0, ""])

        min_path = "z"

        while stack:
            cx, cy, cnt, path = stack.pop()
            for i in range(4):
                nx = cx + dx[i]
                ny = cy + dy[i]
                npath = path + dpath[i]
                ncnt = cnt + 1

                if nx <= 0 or ny <= 0 or nx > n or ny > m or ncnt + get_dist(nx, ny, r, c) > k or (k - ncnt - get_dist(nx, ny, r, c)) % 2 == 1:
                    continue

                ncnt = cnt + 1

                if ncnt == k and nx == r and ny == c:
                    return npath
                elif ncnt < k:
                    stack.append([nx, ny, ncnt, npath])

        return min_path

    answer = dfs()

    if answer == 'z':
        return "impossible"

    return answer