[Level 3 | Python] 미로 탈출 명령어

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

문제

....
..S.
E...

 

왼쪽, 오른쪽, 위, 아래는 문자열 l,r,u,d 로 표현된다. 예를 들어 왼쪽 한칸, 위한칸, 왼쪽 한칸 이면 `"lul"`로 표현된다.

 

S에서 E로 가고 싶다. 갔던 곳 중복 가능하니까 k번 움직여서 E에 딱 도착해야 한다. 가능한가? 불가능한가?

가능하면 표현된 문자열에서 사전 순으로 가장 빠른 경로로 탈출해야 한다. 

불가능하면 "impossible"

풀이 과정

처음에는 dfs로 완전탐색을 돌려서 depth 기준을 k로 잡으면 되겠다 생각했지만, 제한 사항에 k는 2500이기 때문에 4^2500 시간복잡도가 걸리기에 더 효율적인 코드를 작성해야 했다. 

어떻게 가지치기를 해야할지가 고민이 많았던 문제였다. 

맨해튼 거리를 이용해서 갈 수 있는 거리면 DFS를 돌게 하고 아닌 거는 가지치기를 했더니 성공할 수 있었다. 

 

(참고) 맨해튼 거리란?

(x1,y1) 과 (x2,y2)의 최소 거리 : abs(x1-x2) + abs(y1-y2)

맨해튼 거리의 특징은, 두 점 사이의 도로가 모두 x축 또는 y축에 평행한 경우라면, 두 점 사이의 최단거리는 항상 맨해튼 거리와 일치하게 된다는 점이다. 

 

 

 

DFS + 그리디 문제였다. 

시간복잡도
O(4^2500)

import sys
sys.setrecursionlimit(10**6)

def solution(n, m, x, y, r, c, k):
    min_dist = abs(x - r) + abs(y - c)
    
    # 도달 불가능한 경우
    if min_dist > k or (k - min_dist) % 2 == 1:
        return "impossible"

    # 사전순 정렬을 위해 d → l → r → u 순으로 탐색
    dx = [1, 0, 0, -1]  
    dy = [0, -1, 1, 0]  
    wd = ['d', 'l', 'r', 'u']
    
    answer = []

    def dfs(x, y, cnt, path_word):
        # 이미 정답 찾았으면 중단
        if answer:
            return

        # 탈출 조건
        if cnt == k:
            if x == r and y == c:
                answer.append(path_word)
            return
        
        # 사전순 정렬을 위해 d → l → r → u 순서로 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            word = wd[i]
            manhattan_dist = abs(nx - r) + abs(ny - c)

            # 유효한 범위 & 도달 가능성 체크
            if 1 <= nx <= n and 1 <= ny <= m and (manhattan_dist + cnt) <= k:
                dfs(nx, ny, cnt + 1, path_word + word)

    dfs(x, y, 0, "")

    return answer[0] if answer else "impossible"