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

프로그래머스 - 미로 탈출 명령어

# 조건

• n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
• 단, 미로를 탈출하는 조건이 세 가지 있습니다.
  1. 격자의 바깥으로는 나갈 수 없습니다.
  2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
  3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
• 이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
  • l: 왼쪽으로 한 칸 이동
  • r: 오른쪽으로 한 칸 이동
  • u: 위쪽으로 한 칸 이동
  • d: 아래쪽으로 한 칸 이동
• 예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.
• 미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.
• 예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

• 미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다.
• .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.
• 탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.
  1. lldud
  2. ulldd
  3. rdlll
  4. dllrl
  5. dllud
  6. ...
• 이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.
• 격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다.
• 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요.
  • 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

제한사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

# 접근 방법

• 핵심은 도착하지 못하는 경우를 걸러주는 것이다.
  • 남은 거리가 k보다 크다면 impossible을 리턴해주어야 한다.
    • 거리는 맨허튼 거리를 사용하여 abs(x좌표끼리의 차이 + y좌표 끼리의 차이) 를 사용해준다.
  • 또한, k - 최소 거리가 홀수라면 도착점에 k만큼 도착할 수 없으므로 'impossible'
    • 좌표에서 도착할 수 있는 횟수는 최소 거리 + 2의배수씩 증가하기 때문에 최소 거리가 홀수라면 다른 경우도 모두 홀수에 도착하기 때문
    • 짝수인 경우 상하좌우를 밟고 다시 돌아올 수 있으므로..!
  • 도착했는데 남은 거리가 홀수여도 impossible return
• 이제 일반적인 bfs를 돌리며 순회 순서를 d, l, r, u 순서로 방문해준다.
• q에는 (x좌표, y좌표, 이동 횟수, 현재까지 이동 경로)를 넣어주고 도착점까지 탐색해준다.
• 이 때, visited 배열을 사용하는 것이 아닌
  • 남은 거리 + 현재까지 이동 거리가 k보다 크다면 넘어가고, 그렇지 않다면 q에 담아준다.
  • visited 배열을 사용하지 않기 때문에 시간 초과가 발생할 수 있다.
• 시간 초과와 사전순 탐색을 해결하기 위하여 d l r u의 방문 순서로 탐색하므로 최초로 q에 담기는 순간 break를 해준다.
• 즉, d를 최대한 많이 간 후, l을 최대한 많이 가고 r u가 담기게 된다.

from collections import deque

def solution(n, m, x, y, r, c, k):
    answer = ''
    # 남은 거리 탐색 자주 해주어야 하므로 함수로 빼주기
    def manhattan(x1, y1):
        return abs(x1 - (r-1)) + abs(y1-(c-1))

    # k가 최단 거리보다 작거나, 최단 거리 - k가 홀수라면 도착지에 k번만에 도착 불가
    if manhattan(x-1, y-1) > k or (manhattan(x-1, y-1) - k) % 2:
        return 'impossible'
    # 탐색 방향 사전순으로 - d l r u
    direct = {(1,0):'d', (0,-1):'l', (0,1):'r', (-1,0):'u'}
    q = deque()
    q.append((x-1, y-1, 0, ''))
    while q:
        si, sj, cnt, route = q.popleft()
        # 도착했는데 남은 거리가 홀수라면 도착지에 k만큼 오지 못한다!
        if (si, sj) == (r-1, c-1) and (k-cnt) % 2:
            return 'impossible'
        elif (si, sj) == (r-1, c-1) and cnt == k:
            return route
        for di, dj in direct:
            ni, nj = si+di, sj+dj
            if 0<=ni<n and 0<=nj<m:
                # 다음 이동 자리를 보는 것이므로 +1 을 해주어야 함
                if manhattan(ni, nj) + cnt + 1 > k:
                    continue
                q.append((ni, nj, cnt+1, route+direct[(di, dj)]))
                break

    return answer