🐹 미로 탈출 명렁어

1. 문제 링크

미로 탈출 명렁어

2. 코드

dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]
move = ['d', 'l', 'r', 'u']

from collections import deque
import sys

def solution(n, m, x, y, r, c, k):
    sys.setrecursionlimit(5000)
    q = deque([])
    q.append((x, y, 0, ''))
    # 최단 거리 길이
    min_dist = abs(x-r) + abs(y-c)
    
    # 최단 거리보다 이동 가능 거리가 작거나 도달이 불가능한 위치일 때 
    if min_dist > k or (k - min_dist) % 2 == 1:
        return 'impossible'
    
    def find_path(a, b, count, path):
        # k번으로 도달할 수 없는 경우 
        if a == r and b == c and (k-count) % 2 == 1:
            return 'impossible'
        # k번째 도달
        if a == r and b == c and count == k:
            return path
        for i in range(4):
            na = a + dx[i]
            nb = b + dy[i]
            if 0 < na <= n and 0 < nb <= m:
                # 이동 위치가 최종 위치에 도달할 수 없을만큼 멀어질 때 
                if abs(na-r) + abs(nb-c) > k - (count+1):
                    continue
                result = find_path(na, nb, count+1, path + move[i])
                return result
    
    return find_path(x, y, 0, '')

• 정확성

테스트 1 〉	통과 (0.21ms, 10.4MB)
테스트 2 〉	통과 (0.15ms, 10.4MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.03ms, 10.3MB)
테스트 5 〉	통과 (0.04ms, 10.4MB)
테스트 6 〉	통과 (0.02ms, 10.4MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)
테스트 8 〉	통과 (0.03ms, 10.3MB)
테스트 9 〉	통과 (10.15ms, 16MB)
테스트 10 〉	통과 (7.63ms, 16.1MB)
테스트 11 〉	통과 (9.03ms, 16.1MB)
테스트 12 〉	통과 (6.72ms, 16MB)
테스트 13 〉	통과 (7.26ms, 16.1MB)
테스트 14 〉	통과 (8.84ms, 16MB)
테스트 15 〉	통과 (6.66ms, 16.2MB)
테스트 16 〉	통과 (6.79ms, 15.7MB)
테스트 17 〉	통과 (6.54ms, 15.9MB)
테스트 18 〉	통과 (8.29ms, 15.9MB)
테스트 19 〉	통과 (6.31ms, 16.2MB)
테스트 20 〉	통과 (9.90ms, 15.8MB)
테스트 21 〉	통과 (8.67ms, 15.8MB)
테스트 22 〉	통과 (8.65ms, 15.8MB)
테스트 23 〉	통과 (13.91ms, 16.1MB)
테스트 24 〉	통과 (9.83ms, 16.1MB)
테스트 25 〉	통과 (6.76ms, 15.8MB)
테스트 26 〉	통과 (9.31ms, 15.8MB)
테스트 27 〉	통과 (9.86ms, 16MB)
테스트 28 〉	통과 (9.50ms, 15.8MB)
테스트 29 〉	통과 (9.52ms, 16MB)
테스트 30 〉	통과 (9.42ms, 16MB)
테스트 31 〉	통과 (0.01ms, 10.3MB)

3. 해설

이 문제는 불가능한 경우를 잘 걸러내주어 시간을 줄이는 것이 중요하다.

불가능한 경우는 다음과 같다.

1. (x, y) → (r, c)의 최단 경로보다 k(이동 가능 거리)가 작을 때

2. k(이동 가능 거리)에서 (x, y) → (r, c)의 최단 경로 길이를 뺀 길이가 2의 배수가 아닐 때

   → 최단 거리 이동 후 좌,우 혹은 위,아래로 움직여 같은 자리로 돌아올 수 있어야한다.

3. 이동중의 위치에서 최종 위치까지의 거리를 남은 움직임으로 갈 수 없을 때

이때 사전순으로 결과를 찾아야하기 때문에 d(아래), l(왼쪽), r(오른쪽), u(위쪽) 순으로 움직이도록 나열하고 가장 첫 결과를 리턴한다.

처음에는 bfs로 큐를 사용하여 코드를 작성했지만, bfs를 사용하면 최종 목적지로 바로가지않고 주변을 모두 확인하고 최종 목적지로 가기 때문에 시간 초과가 났다.

dfs를 사용하여 최종 목적지까지 바로 갈 수 있도록 코드를 재구현했다. 이때 setrecursionlimit을 하지 않으면 런타임 에러가 뜰 수 있다.