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

https://school.programmers.co.kr/learn/courses/30/lessons/150365?language=python3

프로그래머스

 

 

백트래킹을 통해 구현하였다. dfs를 도는데 방향 순서를 d, l, r, u로 탐색하게 하면 맨 처음 조건을 만족해서 종료되는 시점이 사전순으로 가장 빠르게 됨이 보장된다.

처음 조건을 만족하게 되면 flag=True로 설정하여 나머지 탐색은 즉시 종료한다.

dfs를 돌면서 현재 남은 횟수로 목적지에 도달 가능한지 여부를 판별하여 종료를 한다.

 

 

import sys
sys.setrecursionlimit(10**6)

def solution(n, m, x, y, r, c, k):
    answer = ''
    
    dist = abs(x-r)+abs(y-c)
    if (k-dist)%2==1 or dist > k:
        return 'impossible'

    flag = False
    # d l r u 순서로 dx,dy를 저장
    dx = [1,0,0,-1]
    dy = [0,-1,1,0]
    ch = ['d','l','r','u']
    
    
    def dfs(cx,cy,route,k):
        nonlocal flag,answer
        
        if flag:
            return
        dist = abs(cx-r)+abs(cy-c)
        
        if k == 0 and dist == 0:
            answer=''.join(route)
            # 처음 발견하는 경로가 항상 사전순으로 빠름
            flag = True
            return 
        
        # 도달 불가능하면 종료
        if dist > k or (k-dist)%2==1:
            return
            
        for i in range(4):
            nx,ny = cx+dx[i],cy+dy[i]
            if 1<=nx<=n and 1<=ny<=m:
                route.append(ch[i])
                dfs(nx,ny,route,k-1)
                route.pop()
    
    dfs(x,y,[],k)
    
    return answer