[프로그래머스] 미로 탈출 명령어 (python)
문제 요약
https://school.programmers.co.kr/learn/courses/30/lessons/150365
n x m 크기의 미로에서 (x, y)부터 (r, c)까지 이동하는 경로 중 길이가 k인 경로를 반환하는 문제
1. 지나갔던 칸을 다시 지나갈 수 있음
2. 시작점과 끝점은 다름
3. 상하좌우(uplr)로 이동가능
4. 길이가 k인 경로들 중 문자열이 사전 순으로 가장 빠른 경로를 반환할 것
5. 주어진 조건에 해당하는 경로가 없다면 impossible을 반환
접근
1. 시작점과 도착점의 맨하튼 거리가 홀수이면 가능한 모든 경로의 길이는 홀수이기 때문에 홀/짝이 다르다면 바로 impossible을 반환해주었다.
2. bfs를 사용해 경로의 길이가 k이고 현재 위치와 도착점이 일치하면 경로를 반환했다.
3. 경로를 사전 순으로 가장 빠른 경로를 반환해야하기 때문에 d, l, p, u 순으로 탐색해주었다.
하지만 시간초과가 났다.
틀린 이유
1. 가장 먼저 k가 맨하튼 거리보다 작을 때를 고려해주지 않았다.
2. bfs 안에서 continue와 break를 걸어주지 않아 queue에 필요없는 경로들이 들어가 시간초과가 나왔다.
다른 블로그를 참고했는데 아마 이 부분은 생각해내는데 꽤 오랜 시간이 걸렸을 것 같다.
코드
from collections import deque
def solution(n, m, x, y, r, c, k):
answer = ""
man = abs(x - r) + abs(y - c)
# 맨하튼 거리와 홀짝이 다르거나 k가 맨하튼 거리보다 작으면 안됨
if man % 2 != k % 2 or k < man:
return "impossible"
dirc = {(1, 0): "d", (0, -1): "l", (0, 1): "r", (-1, 0): "u"}
queue = deque([(x, y, 0, "")])
while queue:
i, j, cnt, path = queue.popleft()
if cnt == k and i == r and j == c:
return path
for di, dj in dirc:
a = i + di
b = j + dj
if 1 <= a < n + 1 and 1 <= b < m + 1:
# (여태 온 경로의 길이 cnt + 남은 경로의 최단거리)가 k와 같다면 이미 queue에 정답이 있다. 크다면 queue에 들어갈 이유가 없고.
if cnt + abs(a - r) + abs(b - c) >= k:
continue
queue.append((a, b, cnt + 1, path + dirc[(di, dj)]))
# queue에 경로를 하나 넣어주었다면 그게 사전 순으로 가장 빠른 경로이므로 더 넣어줄 필요 x
break
회고
for idx, (a, b) in enumerate([(i + 1, j), (i, j - 1), (i, j + 1), (i - 1, j)]):
if 1 <= a < n + 1 and 1 <= b < m + 1:
if idx == 0:
queue.append((a, b, cnt + 1, path + "d"))
elif idx == 1:
queue.append((a, b, cnt + 1, path + "l"))
elif idx == 2:
queue.append((a, b, cnt + 1, path + "r"))
elif idx == 3:
queue.append((a, b, cnt + 1, path + "u"))
처음에 bfs에서 상하좌우를 탐색했을 때 이렇게 코드를 짰었다.
이렇게 쓰면 이 문제에서는 반복코드가 많아지기 때문에 딕셔너리를 사용하거나 배열을 사용하는 것이 훨씬 효율적인 것 같다.
dfs로 푸는 방법도 있던데 시간날 때 도전 해볼 것..
꼭 돌아와서 이 자리에 채울 것!
지금 당장은 다른 문제를 풀러가야함