문제 - 미로 탈출 명령어

문제설명

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

 

고민한 점

1. impossible 출력을 위해 |x-r| + |y-c|와 k의 차이가 1인경우와 |x-r| + |y-c|가 k보다 큰경우를 처리
2. 경로를 찾을 때 완전탐색으로 모든 경로를 배열에 담은 뒤 정렬한뒤에 첫번째 요소 출력
3. 완전탐색을 DFS로 구현
4. 메모리 초과 발생 => 완전탐색으로 인해 배열의 길이가 초과됨
5. 그리디 탐색으로 사전 순으로 빠른 순서로 경로를 선택