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

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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : DFS, BFS 
풀이 시간 : 32분 

문제 풀이 

총 k번 이동하여 미로를 탈출할 수 있는 문자열 경로 중 사전 순으로 가장 빠른 경로를 출력하는 문제이다.

 

문제의 조건 중 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 라는 조건이 있다. 이를 통해 같은 격자를 중복해서 방문해도 된다는 것으로 확인할 수 있다.

 

우리는 최단경로를 찾기 위해 DFS, BFS 와 같은 그래프 탐색 알고리즘을 사용할 수 있다. 이번에는 DFS를 사용해서 풀어보자.

 

근데 여기서, 문제점이 있다. 입력 변수들의 범위를 살펴보면, 갈 수 있는 경로의 길이 k가 $k ≤ 2500$으로 주어진다. 최악의 경우 DFS 탐색을 하게 된다면, $O(4^{2500})$의 시간복잡도가 걸리기 때문에, 무조건 시간초과가 발생하게 된다.

 

따라서, 우리는 가지치기를 진행해주어야 한다. 

총 진행할 수 있는 가지치기는 세가지가 있다.

 

1. 출발지부터 목적지까지의 총 거리가 k보다 크거나 $k - 총 거리$가 홀수라면, 이동이 불가능하다.

2. 새로 생성되는 경로가 현재 answer 경로보다 사전 순으로 뒤쳐지는 경우, 이동이 불가능하다.

3. 이동 경로가 k를 넘어서면, 이동이 불가능하다.

 

1번 가지치기의 경우, k보다 총 이동거리가 크다면 절대 못가는 경우가 발생하고, 만약, k가 총 거리보다 큰 경우라면, 무조건적으로 한 지점을 찍고 다시 돌아와야하기 때문에, 두 번의 이동이 추가로 필요하게 된다.

2번 가지치기의 경우, 문제 조건에서 사전 순으로 출력해야 하기 때문에, 가지치기를 진행해주었다. 이에 따라, 시작 전에 `answer = 'z'`로 초기화를 진행해주었다.

3번 가지치기의 경우, k번만큼만 이동해야 하기 떄문에 설정해주었다.

 

코드

'''
1. 격자 바깥으로 나가기 불가능
2. 이동하는 총 거리가 k여야 함. 같은 격자를 2번 이상 방문해도 괜찮음
3. 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.

d, l, r, u 순으로 이동해보기

풀이 : dfs, 이동거리가 총 k가 되었을 때만 빠져나오도록 함
k를 넘어서면 continue -> 재귀 깊이 총 2500보다 작다
같은자리 있을 수는 없지만, 뺑뺑 돌 수는 있음
'''

import sys
sys.setrecursionlimit(10**7)

dir_dict = {0: 'd', 1: 'l', 2: 'r', 3: 'u'}
dr = [1, 0, 0, -1]
dc = [0, -1, 1, 0]

answer = 'z'

def dfs(depth, r, c, er, ec, path, k, n, m):
        global answer
        # 가지치기 3. 이동거리가 k를 넘어서는 경우
        if depth > k:
            return
        if depth == k and (r, c) == (er, ec):
            answer = path
            return
        for d in range(len(dr)):
            nr, nc = r + dr[d], c + dc[d]
            # 가지치기 2. 새로 생성되는 경로가 answer보다 크거나 같은 경우
            if 0 <= nr < n and 0 <= nc < m and path < answer:
                dfs(depth + 1, nr, nc, er, ec, path + dir_dict[d], k, n, m)
            

def solution(n, m, x, y, r, c, k):
    global answer
    
    # 굳이 grid 만들 필요 없음
    er, ec = r - 1, c - 1
    # 초반부터 종료조건 걸기
    # 가지치기 1. k만큼 이동하여 도착할 수 없거나, k가 dist보다 큰 경우, 찍고 돌아오지 못하는 경우
    dist = abs(x - r) + abs(y - c)
    if dist > k or (k - dist) % 2 == 1:
        return "impossible"
    
    dfs(0, x - 1, y - 1, er, ec, "", k, n, m)
    
    return answer

배운 점 

dfs의 시간복잡도를 계산하는 과정에서 어떤 동작에 대해 재귀적으로 수행하는지를 파악하고, 시간복잡도를 계산하는 능력을 기를 수 있었다. 두 가지 경우에 대해서만 탐색하는지 or 여러가지 경우에 대해 탐색하는지 파악할 필요가 있어보인다.