[프로그래머스] 미로 탈출 명령어

import sys
sys.setrecursionlimit(10**6)
def solution(n, m, x, y, r, c, k):
    dx = [1, 0, 0, -1] #남서동북
    dy = [0, -1, 1, 0]
    
    info = {
        0 : 'd',
        1 : 'l',
        2 : 'r',
        3 : 'u'
    }
    res = "impossible"
    flag = False
    visited = []

    def dfs(i, j, cnt):
        nonlocal res, flag, visited
        if flag : return
        #k안으로 어차피 못갈 바에 return
        if abs(r-i)+abs(c-j)+cnt > k: 
            return

        #도착했으면 flag로 막아주기
        if cnt == k and i == r and j == c:
            res = ''.join(visited)
            flag = True
            return
        
        for p in range(4):
            di = i + dx[p]
            dj = j + dy[p]

            if di <=0 or dj <=0 or di>n or dj>m: continue
            visited.append(info[p])
            dfs(di, dj, cnt+1)
            visited.pop()

    
    dist = abs(x-r) + abs(y-c)
    if dist <= k and (k-dist)%2 == 0:
        dfs(x, y, 0)
    return res

1. dfs를 돌릴 후보들을 결정해줍니다.

    시작점 - 도착점 거리가 k보다 크면 아예 갈 수가 없고,

    시작점 - 도착점까지의 거리를 구했을 때, 거리가 짝수면 짝수번만에 도착할 수 있고, 홀수면 홀수번만에 도착할 수 있습니다. 

2. dfs의 종료조건은 도착점에 도착했으며, 이때까지 이동한 거리가 k일 때입니다.

    flag변수를 사용해서 다 return을 시켜서 dfs를 빠져나가 줍니다.

3. dfs의 가지치기 조건은 특정 좌표에서 도착지점까지 남은 거리를 계산했는데, 이미 온 거리랑 남은 거리의 합이 k보다 큰 경우입니다.

4. 문자열이 작은 순서로 방문해야하므로 dx, dy의 순서를 문자열 순으로 해서 for문을 돌려줍니다.