[프로그래머스 Lv3, python] - 미로 탈출 명령어

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

프로그래머스

# 내 풀이..
import sys
sys.setrecursionlimit(5000)
def solution(n, m, x, y, r, c, k):
    pos = []
    direct = [[1,0],[0,-1],[0,1],[-1,0]]
    # 만약 탈출지점에 도착했더라도 끝낼수없음. 거리가 k여야함.. 같은 곳 가도 됨.=> K이하까지만 탐색하기..
    def dfs(px, py, st):
        if len(st) == k: # 다 도달했음.
            if [r-1,c-1] == [px,py]: # 도착지점임.
                if len(pos) == 0: # 순서대로 접근하기 때문에 처음에 도착하는 곳이 제일 빠름!
                    pos.append(st)
            return
        
        if pos:
            return
        
        for x, y in direct:
            dx, dy = px + x, py + y
            dist = abs(dx - (r-1)) + abs(dy - (c-1))
            remain = k - (len(st) + 1)  

            if dist > remain:
                continue
            if (remain - dist) % 2 == 1:
                continue
            if 0 <= dx < n and 0 <= dy < m: # 이동 가능 
                if [x,y] == [0,1]: # 오른쪽 이동
                    dfs(dx,dy,st+'r')
                elif [x,y] == [1,0]: # 아래쪽 이동
                    dfs(dx,dy,st+'d')
                elif [x,y] == [0,-1]: # 왼쪽 이동
                    dfs(dx,dy,st+'l')
                elif [x,y] == [-1,0]: # 위쪽 이동
                    dfs(dx,dy,st+'u')
                
    
    dfs(x-1,y-1,'')

    if pos:
        return pos[0]
    
    return "impossible"

# 지피티가 최적화한 풀이(그리디 사용)
def solution(n, m, x, y, r, c, k):
    x -= 1
    y -= 1
    r -= 1
    c -= 1

    dist = abs(x - r) + abs(y - c) # 출발지에서 목적지 맨해튼 거리

    if dist > k or (k - dist) % 2: # k보다 크거나 차이가 홀수이면 불가능함.
        return "impossible"

    answer = []

    directions = [ # 사전순서대로 배치
        (1, 0, 'd'),
        (0, -1, 'l'),
        (0, 1, 'r'),
        (-1, 0, 'u')
    ]

    for step in range(k):
        for dx, dy, ch in directions:
            nx = x + dx
            ny = y + dy

            if not (0 <= nx < n and 0 <= ny < m):
                continue

            remain = k - step - 1 # 남은 횟수
            new_dist = abs(nx - r) + abs(ny - c) # 남은 거리
            
			# 남은 횟수보다 크거나 차이가 홀수이면 불가능함.
            if new_dist <= remain and (remain - new_dist) % 2 == 0: 
                answer.append(ch)
                x, y = nx, ny
                break

    return ''.join(answer)