문제 설명
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" |
풀이
오답 접근법.
BFS 로 완전 탐색하여 가장 먼저 도착하는 것이 정답이겠다 → X
가장 먼저 도착한게 사전 순으로 가장 빠른게 아니구나, answer에 min을 해줘야겠다. → 시간 초과
아, 사전 순으로 가장 빠른 길이 정답이니까 min heap 으로 관리하면 되겠다. → 시간 초과
아 목적지까지는 중복을 제외한 최단 경로로 도착하고, 그 뒤 부터 중복을 허용하면 시간이 짧아지겠다. → X + 시간 초과
결론적으로 BFS 탐색은 무조건 시간 초과구나 싶었다.
사실 미로의 최대 범위가 50 x 50 이고, 이걸 최대 4번씩 반복하니까 (50*50)^4 라서 이미 말도안되는 연산 숫자가 나온다.
그러면 새로운 방법을 찾아야한다.
우선 탈출을 못하는 경우는 제외하고 시작한다.
- 탈출 지점까지의 최소 거리가 k 보다 큰 경우 → 아무리 빨리 가도 k 안에 탈출 불가능
- 탈출 지점까지 이동 후 남은 거리가 홀수인 경우 → 탈출 지점에 도착 한 뒤 반드시 홀수번 이동해야 하므로 탈출 지점에 도달할 수 없음.
위 두가지 경우는 탈출 할 수 없는 경우이다.
위 조건에서 벗어나는 경우 탈출 할 수 있다는 말이다.
그러면 가장 사전순으로 빠른 순서인 d, l, r, u 순서로 미로 탈출을 시도 해야한다.
d 연산을 수행하는 최소 횟수는 출발지의 y 위치 (문제에서는 x로 주어짐;;) - 목적지 r 위치이다. 근데 y 가 r보다 작은 경우도 존재할 땐 d 연산을 수행할 필요가 없으므로 max(r - y, 0)
l 연산도 마찬가지로 max(x - c, 0)
r 연산도 max(c - x, 0)
u 연산도 max(y - r, 0)
그리고 마지막으로 움직임을 상쇄시켜줄 수 있는 pair 횟수를 구한다.
pair 는 k에서 출발지로 부터 목적지까지 최단 거리를 뺀 값의 2를 나누면 된다.
pair = (k - distance) // 2
이렇게 되면 우리는 필요한 연산 횟수와 상쇄 할 수 있는 횟수를 구하게 된 것이다.
dlru 순서대로 탈출을 시도하면 되므로, k번 만큼 for-loop를 통해 움직인다.
d 연산을 수행할 수 있는 경우는 다음과 같다.
현재 위치 + 1 이 범위 안에 있을 때, d 연산이 남아있는 경우 혹은 pair 로 움직임을 상쇄할 수 있는 경우
만약 d 연산이 남아있었다면, d -= 1을 해주면 되는 것이고, 그렇지 않고 pair 가 남아있었다면, pair -= 1 을 해줘서 상쇄 횟수를 차감하고 u += 1을 통해 상쇄에 필요한 요소를 더해준다.
모든 연산을 위와 같은 방법으로 진행하면, k 번의 for-loop가 끝났을 때, 최단 거리가 생성된다.
코드
from heapq import heappop, heappush
from copy import deepcopy
def solution(n, m, y, x, r, c, k):
answer = ''
maps = [[' ' for _ in range(m + 1)] for _ in range(n + 1)]
maps[y][x] = 'S'
maps[r][c] = 'E'
distance = abs(y - r) + abs(x - c)
if distance > k:
print('impossible')
return 'impossible'
if (k - distance) % 2 != 0:
print('impossible')
return 'impossible'
# dlru
down = max(r - y, 0)
left = max(x - c, 0)
right = max(c - x, 0)
up = max(y - r, 0)
pair = (k - distance) // 2
for _ in range(k):
if (down or pair) and y < n:
answer += 'd'
if down:
down -= 1
else:
pair -= 1
up += 1
y += 1
elif (left or pair) and x > 1:
answer += 'l'
if left:
left -= 1
else:
pair -= 1
right += 1
x -= 1
elif (right or pair) and x < m:
answer += 'r'
if right:
right -= 1
else:
pair -= 1
left += 1
x += 1
else:
answer += 'u'
if up:
up -= 1
else:
pair -= 1
down += 1
y -= 1
print(answer)
return answer
