[프로그래머스 / Python] 미로 탈출 명령어 (DFS)

문제

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

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

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

 

풀이

• 깊이 우선 탐색(DFS) 알고리즘을 활용하여 경로를 찾을 수 있다.
  • DFS 알고리즘은 LIFO(Last In First Out)의 특징을 갖고 있기 때문에 사전순으로 앞서는 알파벳을 뒤에서 탐색한다면 항상 사전순으로 빠른 문자열을 먼저 탐색할 수 있다.
• 탐색 방향을 u, r, l, d 순으로 설정한다.
  • 한 노드에서 상하좌우로 이동할 때 u, r, l, d 순으로 탐색한다면, 가장 나중에 탐색한 d에 이어서 탐색을 이어나가기 때문에 항상 사전순으로 빠른 문자열을 탐색할 수 있다.
• 탐색 조건을 확인한다.
  • in_range : 탐색 시 격자 밖으로 나가지 않도록 확인한다.
  • reachable : 이동 거리가 k를 만족하지 못하는 경우 탐색을 멈추도록 설정한다.
    • 현재 위치와 도착지까지의 맨해튼 거리($|x1-x2|+|y1-y2|$)를 dist라고 했을 때,
    • 남은 이동거리(rest)에서 dist를 뺀 값이 양수면서 짝수라면 True를 반환하고
    • 그렇지 않으면 이동하지 못함으로 False를 return 한다.
    • rest-dist가 짝수인 조건을 추가한 이유는 도착지에 도착하고도 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"

 

문제출처

프로그래머스