[프로그래머스] 150365. 미로 탈출 명령어 | 그리디, BFS | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• n*m 격자 미로가 있을 때 (x, y)에서 (r, c)로 이동해야 한다. 
• (x, y)에서 (r, c)까지의 총거리는 k여야 한다. (같은 위치 중복 이동 가능)
• 이동경로는 l(왼쪽), r(오른쪽), u(위쪽), d(아래쪽)으로 나타낸다.
• 미로에서 탈출하는 경로를 문자열로 나타냈을 때 사전순으로 가장 빠른 경로를 구하라. 
  만약 탈출할 수 없다면 impossible을 반환하라.

---

문제 조건

• 2 <= n, m <= 50
• 1 <= x, r <= n, 1 <= y, c <= m, (x, y) != (r, c)
• 1 <= k <= 2500

---

시행착오

• 처음에는 dfs로 모든 경로를 탐색한 후 사전순으로 나열했을 때 가장 빠른 경로를 구하려고 했는데 당연히 시간초과
• '질문하기'에서 힌트를 보았다. ㅎ

---

핵심 전략

• 일단 (x, y)에서 (r, c)까지의 최소거리가 짝수이면 k도 짝수여야 하고, 홀수이면 k도 홀수여야 한다.
• 그리디로 해결해야 한다.(시간제한때문) 만약 d로 시작하는 경로가 가능하면 l, r, u는로 시작하는 경로는 고려하지 않는다. 
• 새로운 이동경로를 추가할 때 격자 밖으로 나가지 않고, (r, c)까지의 거리가 k를 넘지 않는지 검사해야 한다.

---

소스코드

from collections import deque

dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]
command = "dlru"

def solution(n, m, x, y, r, c, k):
    min_distance = abs(r-x) + abs(c-y)
    if k < min_distance or min_distance%2 != k%2:
        return "impossible"

    q = deque([('', x, y, 0)])
    while q:
        s, x, y, cnt = q.popleft()
        if cnt == k:
            continue

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 < nx <= n and 0 < ny <= m:
                if cnt + 1 == k and nx == r and ny == c:
                    return s+command[i]

                if abs(r-nx) + abs(c-ny) + cnt + 1 > k: continue

                q.append((s+command[i], nx, ny, cnt+1))
                break

    return "impossible"