[Programmers / Python] 미로 탈출 명령어 (DFS)

문제

NxM 크기의 격자 미로 안에서 출발지 (x, y)에서 도착지 (r, c)로 가는 경로를 알파벳으로 표기했을 때, 사전 순으로 가장 빠른 경로를 찾는 문제이다.

미로를 탈출하기 위해서 이동하는 거리는 k여야 한다. ( 이동거리 = 이동 횟수 = 경로 문자열 길이 )

경로는 u(상), d(하), l(좌), r(우) 로 표현 가능하며 사전 순으로 가장 빠른 경로를 선택한다.

 

풀이

• 깊이 우선 탐색(DFS) 알고리즘을 활용하여 경로를 찾을 수 있다.
• DFS 알고리즘은 LIFO(Last In First Out)의 특징을 갖고 있기 때문에 사전순으로 앞서는 알파벳을 뒤에서 탐색한다면 항상 사전순으로 빠른 문자열을 먼저 탐색할 수 있다.
• 한 노드에서 상하좌우로 이동할 때 u, r, l, d 순으로 탐색한다면, 가장 나중에 탐색한 d에 이어서 탐색을 이어나가기 때문에 항상 사전순으로 빠른 문자열을 탐색할 수 있다.
• 이때 사전에 주어졌던 격자 밖으로 나갈 수 없다는 조건(in_range)을 추가하고, 
• 경로 이동 중 만약 이동거리 k를 만족하지 못하는 경우가 생긴다면 탐색을 멈추는 조건(reachable)을 추가하여 문제를 풀 수 있다.
• reachable 함수는 남은 이동거리에서 현재 위치에서 도착지까지의 맨해튼 거리(|x1-x2|+|y1-y2|)를 뺏을 때 값이 양수면서 짝수일 때 True를 아니면 이동하지 못함으로 False를 return 한다.
  • 짝수인 이유는 도착지에 도착하고도 k에 못 미치면 이동거리가 k가 될 때까지 다른 곳으로 이동했다가 돌아오는 거리를 추가해야 하기 때문이다.

 

Python 코드

def solution(n, m, x, y, r, c, k):
    # 범위 내인지 확인
    def in_range(xx,yy):
        return 0<xx<=n and 0<yy<=m
    
    # 이동거리 k를 만족하는지 확인
    def reachable(cur,end,rest):
        dist = abs(cur[0]-end[0])+abs(cur[1]-end[1])
        if rest >= dist and (rest-dist)%2 == 0:
            return True
        return False
    
    # 처음부터 거리가 안되는 경우 제외
    if not reachable((x,y),(r,c),k):
        return "impossible"
    
    stack = [("",x,y,k)]
    while stack:
        l,cx,cy,cd = stack.pop()
        
        # 남은 거리가 없는 경우 도착지라면 정답 return
        if cd == 0:
            if cx == r and cy == c:
                return l
            continue
        
        for dx,dy,a in [(-1,0,"u"),(0,1,"r"),(0,-1,"l"),(1,0,"d")]:
            nx,ny,nl = cx+dx, cy+dy, l+a
            if not in_range(nx,ny):
                continue
            if not reachable((nx,ny),(r,c),cd-1):
                continue
            stack.append((nl,nx,ny,cd-1))   
    
    return "impossible"

 

문제출처

프로그래머스