[알고리즘][RE] 미로 탈출 명령어

문제 설명
n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

격자의 바깥으로는 나갈 수 없습니다.
(x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

l: 왼쪽으로 한 칸 이동
r: 오른쪽으로 한 칸 이동
u: 위쪽으로 한 칸 이동
d: 아래쪽으로 한 칸 이동
예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

lldud
ulldd
rdlll
dllrl
dllud
...
이때 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
입출력 예
n	m	x	y	r	c	k	result
3	4	2	3	3	1	5	"dllrl"
2	2	1	1	2	2	2	"dr"
3	3	1	2	3	3	4	"impossible"
입출력 예 설명
입출력 예 #1

문제 예시와 동일합니다.

입출력 예 #2

미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

S.
.E
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

rd
dr
"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

입출력 예 #3

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

.S.
...
..E
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

따라서 "impossible"을 return 해야 합니다.

나의 풀이

- 알고리즘 유형은 그리디(항상 최선의 선택을 할 방법이 있다)이고 자료구조로는 heap을 활용하면 된다.

- 핵심 아이디어는 무조건 가야하는 heap 자료구조인 exact_ways와 남아서 왔다갔다해야 하는 움직임 간에 비교를 하고 exact_ways가 사전 순으로 앞선다면 그걸 차용한다.

- 그렇지 않으면 추가 움직임에서 차용하고 다시 돌아오는 움직임을 exact_ways에 넣어준다.

- 이걸 추가적으로 움직여야 하는 거리만큼 하고 다하면 꼭 움직여야 하는 거리만 남은 거기 때문에 exact_ways에서 차례로 뽑아준다.

- 이 구현 자체는 자료구조 시간에 배운 merge sort 부분에서 merge 할 때의 알고리즘과 유사하다.

- 그 알고리즘에서는 두 개의 리스트를 비교해서 작은 걸 새로운 리스트에 넣어주는 식으로 정렬한다. 그리고 하나가 끝나면 남은 건 뒤에 주르륵 붙여준다. 

- heap에 익숙해지도록 한번쯤 다시 풀어보면 좋을 듯하다.

import heapq

def solution(n, m, x, y, r, c, k):
    # k 방향대로 움직이는데 그 중 가장 사전순으로 빠른 값을 구해야 한다.
    # 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수 있는 방법이 있으므로 그리디
    # 중간 결과를 이용할 방법이 없으므로 DP
    # 완전 탐색을 하기에는 4^2500이 되므로 시간 초과
    # d, l, r, u 순이다.
    # 이 순으로 가도록 하면 된다.
    # (x, y) 와 (r, c)의 차이를 먼저 구하고
    # 남는 것은 d, l, r, u 순으로 움직이는데
    # d와 u가 최대한 움직이면 움직인다.
    # 더 이상 못 움직이면 l, r이 움직인다
    
    left_right = c - y
    up_down = r - x
    
    # 남은 거리를 이용한 impossible 조건
    leftover = (k - abs(left_right) - abs(up_down))
    if leftover < 0 or leftover % 2 != 0:
        return "impossible"
    
    exact_ways = []
    if left_right >= 0:
        # right
        exact_ways.extend([2] * abs(left_right))
    else:
        # left
        exact_ways.extend([1] * abs(left_right))
        
    if up_down >= 0:
        # down
        exact_ways.extend([0] * abs(up_down))
    else:
        # up
        exact_ways.extend([3] * abs(up_down))
    
    heapq.heapify(exact_ways)
    
    dx = [1, 0, 0, -1]
    dy = [0, -1, 1, 0]
    answer = []
    cur_pos = (x, y)
    
    while leftover > 0:
        cur_x, cur_y = cur_pos
        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            if (1<=nx<=n and 1<=ny<=m):
                break
        if exact_ways and i >= exact_ways[0]:
            index = heapq.heappop(exact_ways)
            nx = cur_x + dx[index]
            ny = cur_y + dy[index]
            answer.append(index)
            cur_pos = (nx, ny)
            
        else:
            leftover -= 2
            heapq.heappush(exact_ways, 3-i)
            answer.append(i)
            cur_pos = (nx, ny)
            
    while exact_ways:
        idx = heapq.heappop(exact_ways)
        answer.append(idx)
    
    dict = {0:"d", 1: "l", 2: "r", 3:"u"}
    answer = ''.join(map(lambda x: dict[x], answer))
    
    return answer