문제
- $n \times m$ 미로가 있다. (x, y) -> (r, c) 로 탈출하는 경로 리턴하기
- 2 <= n, m <= 50
- (x, y) ≠ (r, c)
- l 왼쪽, r 오른쪽, u 위쪽, d 아래쪽 으로 이동할 수 있다.
- 이동 거리가 총 k여야 하고, 중복 방문해도 된다.
- 경로를 문자열로 표현했을 때 사전 순으로 가장 빠른 경로로 탈출해야 한다.
- 미로 탈출할 수 없는 경우 "impossible" 리턴
풀이 1
- 사전 순으로 제일 빠른 경로 하나만 탐색하면 되니까 DFS 사용
- 전체 경로를 탐색하면 $O(4^{2500})$ 으로 시간 초과 나니까 정답 찾으면 멈춰야 한다.
테스트 케이스 4~8번 제외하고 시간 초과
import sys
sys.setrecursionlimit(10**4)
def solution(n, m, x, y, r, c, k):
dx = (1, 0, 0, -1) # dlru 순서
dy = (0, -1, 1, 0)
ds = ('d', 'l', 'r', 'u')
answer = []
def dfs(x, y, string, move):
if move == k : # k번 움직였고
if x == r and y == c: # 도착한 경우
answer.append(string)
return True
else : # 도착 못한 경우
return False
# d, l, r, u 순으로 탐색
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 < nx <= n and 0 < ny <= m and not answer:
if dfs(nx, ny, string[:]+ds[i], move+1) :
break
dfs(x, y, "", 0)
if answer:
return answer[0]
else:
return "impossible"
풀이 2
- impossible 조건 추가
- 최소 이동 횟수 : abs(도착지 x 좌표 - 현재 x 좌표) + abs(도착지 y 좌표 - 현재 y 좌표)
- 최소 이동 횟수가 k보다 많거나,
- 최소 이동 횟수 제외한 이동 횟수가 홀수인 경우에는 도착지에 도착 불가능
- 종료 조건 추가
- 남은 이동 횟수 안에 도착지까지 갈 수 없는 경우 탐색 멈추기
통과!
import sys
sys.setrecursionlimit(10**4)
dx = (1, 0, 0, -1) # dlru 순서
dy = (0, -1, 1, 0)
ds = ('d', 'l', 'r', 'u')
answer = ''
def dfs(x, y, string, move, n, m, r, c, k):
global answer
# 남은 횟수 안에 도착지까지 갈 수 없는 경우 stop
if k < move + abs(x - r) + abs(y - c):
return
# 정답을 찾은 경우
if move == k and x == r and y == c:
answer = string
return
# 사전 순으로 탐색
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 < nx <= n and 0 < ny <= m and not answer:
dfs(nx, ny, string[:]+ds[i], move+1, n, m, r, c, k)
def solution(n, m, x, y, r, c, k):
min_move = abs(r-x)+abs(c-y) # 도착지까지의 최소 이동 횟수
# 최소 이동 횟수가 k보다 많거나,
# 최소 이동 횟수 제외한 이동 횟수가 홀 수인 경우에는 도착지에 도착 불가능
if min_move > k or (k - min_move) % 2 == 1:
return "impossible"
dfs(x, y, "", 0, n, m, r, c, k)
return answer
풀이 3
- 위와 동일한 코드인데 재귀가 아닌 반복문을 이용한 DFS
- 반복문이라 더 빠를 것으로 예상했는데 의외로 더 느렸다.
- 이 코드는 평균 8ms 인데, 재귀 이용한 코드는 평균 6ms
통과!
from collections import deque
def solution(n, m, x, y, r, c, k):
dx = (-1, 0, 0, 1) # urld 순서
dy = (0, 1, -1, 0)
ds = ('u', 'r', 'l', 'd')
answer = ""
total_move = abs(r-x)+abs(c-y)
if total_move > k or (k - total_move) % 2 == 1:
return "impossible"
q = deque([(x, y, "", 0)])
while q:
x, y, string, move = q.pop()
if move == k and x == r and y == c :
return string
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 < nx <= n and 0 < ny <= m and k >= move + abs(r-x) + abs(c-y) :
q.append((nx, ny, string+ds[i], move+1))
return answer
풀이 4
- BFS로 풀 수는 없을까..?
- 시간 초과 나는데, visited 추가하면 통과 된다. (근데 느림)
- 시간 초과를 해결 못해서 다른 분 코드를 참고했는데 visited가 어떤 면에서 경우의 수를 차단해주는지 모르겠다. 탐구 필요!
from collections import deque
def solution(n, m, x, y, r, c, k):
dx = (1, 0, 0, -1) # dlru 순서
dy = (0, -1, 1, 0)
ds = ('d', 'l', 'r', 'u')
answer = ""
total_move = abs(r-x)+abs(c-y)
if total_move > k or (k - total_move) % 2 == 1:
return "impossible"
q = deque([(x, y, "", 0)])
# visited[x][y][k] : x, y 에서 k번째 움직였을 때 문자열
visited = [[[False]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
visited[x][y][0] = True
while q:
x, y, string, move = q.popleft()
if move == k and x == r and y == c :
return string
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if 0 < nx <= n and 0 < ny <= m and k >= move + abs(r-x) + abs(c-y) and not visited[nx][ny][move+1]:
visited[nx][ny][move+1] = True
q.append((nx, ny, string+ds[i], move+1))
return answer
References
