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

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

프로그래머스

문제 설명

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

---

방향이 4가지 k가 최대 2500이라 DFS 가 힘들어 보일 수 있지만 안 되는 경우가 많아 백트래킹으로 풀 수 있다.

1. 남은 움직임 수가 현재 위치에서 목표지점까지의 거리보다 적으면 가지치기

2. 남은 움직임 수에서 현재 위치에서 목표지점까지의 거리를 뺐을 때 홀수번 남으면 가지치기

    - 이는 어디서든 최단 루트에서 벗어났다가 돌아오는데 짝수번이 필요하기 때문이다.

3. Down -> Left -> Right -> Up 순으로 확인

 

---

처음에 4^2500 승이 걸리는 줄 알고 DFS가 아닌 규칙을 찾아보려 했다. 아무리 생각해도 규칙을 찾을 수 없었다. 그래서 검색을 해보니 가지치기를 했으면 됐던 것이다! 그래프 문제에서도 요즘 BFS를 많이 풀다 보니 백트래킹을 미처 생각하지 못했다. 곰곰이 생각해 보니 실제로 갈 수 없는 길이 많을 것 같았다. 친구가 옛날에 풀었을 때 k의 최댓값이 함정이라고 그랬는데 무슨 의미인지를 이제야 알겠다! 이 문제를 풀어보길 잘한 것 같다.