https://school.programmers.co.kr/learn/courses/30/lessons/150365
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
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 해야 합니다.
문제에서 같은 격자를 두 번 이상 방문할 수 있다고 했으므로 다익스트라 알고리즘을 금방 떠올릴 수 있다.
문제를 풀기 위해 힙 자료구조와 다익스트라 알고리즘을 사용했다.
첫 번째 문제 예시에서 3x4행렬이 있고, k=5이므로 E의 자리에는 길이가 5인 사전 순으로 가장 앞선 문자열이 와야 한다.
E 위치의 주변 자리들은 E에서 떨어진 거리에 따라 가능한 최대 문자열의 길이가 다르다.
그렇게 각 자리의 문자열의 최대 길이는 k-(|y-r| + |x-r|) 이어야 한다.
....
..S.
E...
| 3 | 2 | 1 | 0 |
| 4 | 3 | 2 | 1 |
| 5 | 4 | 3 | 2 |
힙을 사용하면 가장 사전순으로 앞선 문자열들이 먼저 나오는 것이 보장된다.
그렇기 때문에 문자열의 길이가 k-(|y-r| + |x-r|) 이고 기존 문자열의 길이보다 길다면 힙에 넣어준다.
distance = abs(ny - r) + abs(nx - c)
if len(s+alpha[i]) <= k-distance and len(dist[ny][nx]) < len(s+alpha[i]):
heappush(heap, [s+alpha[i], ny, nx])
dist[ny][nx] = s + alpha[i]
<< 전체 코드 >>
from heapq import heappush, heappop
def solution(n, m, y, x, r, c, k):
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
alpha = ['u', 'd', 'l', 'r']
dist = [['' for _ in range(m+1)] for _ in range(n+1)]
heap = [['', y, x]]
while heap:
s, y, x = heappop(heap)
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny <= 0 or ny > n or nx <= 0 or nx > m:
continue
# 문자열의 길이가 k-(|y-r| + |x-r|) 이고 기존 문자열의 길이보다 길다면 힙에 넣어준다.
distance = abs(ny - r) + abs(nx - c)
if len(s+alpha[i]) <= k-distance and len(dist[ny][nx]) < len(s+alpha[i]):
heappush(heap, [s+alpha[i], ny, nx])
dist[ny][nx] = s + alpha[i]
if len(dist[r][c]) < k: # k번 이동하지 못한 경우
return 'impossible'
return dist[r][c]편의를 위해 x와 y를 바꿔서 표시했다.