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

난이도 : LV3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

문제해결

• 일단 가독성을 높이기 위해 각각의 좌표를 -1씩 더했다.
• direction 리스트의 순서를 사전순 ['d', 'l', 'r', 'u'] 으로 나타냈다. dfs 탐색시 가장 빠르게 정답을 발견할수 있도록
• dfs 의 리턴조건은 다음과 같다.
  • 완성된 문자열의 길이가 조건과 같은 경우
  • 아직 완성되지는 않았지만 현재까지 가장 작은문자열보다 큰 경우 (파이썬은 문자를 아스키 코드를 통한 크기 비교가 가능하다)
  • 목표지점 까지의 최단거리가 남은 이동가능 횟수보다 큰 경우
  • 목표지점 까지의 최단거리와 남은 이동가능 횟수의 2로 나눈 나머지가 다른경우 (각각 짝수와 홀수로 다르면 목표지점까지 횟수를 다사용해서 이동 불가)

소스코드

import sys

sys.setrecursionlimit(10**8)

minVal = 'z' # 아스키코드가 가장 높은 문자
dx,dy = [1,0,0,-1], [0,-1,1,0]
def solution(n, m, x, y, r, c, k):
    x -= 1
    y -= 1
    r -= 1
    c -= 1
    direction = ['d', 'l', 'r', 'u']
    def dfs(a,b,s):
        global minVal
        
        if len(s) == k:
            if a == r and b == c and s < minVal:
                minVal = s            
            return
        
        if s > minVal:
            return
        
        if abs(a - r) + abs(b - c) > k - len(s) or (abs(a - r) + abs(b - c)) % 2 != (k - len(s))%2:
            return
        
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<n and 0<=ny<m:
                dfs(nx,ny, s+direction[i])
    dfs(x,y,'')
    if minVal == 'z':
        return 'impossible'
    else:
        return minVal

여담

아무리봐도 맞는것 같은데 자꾸 시간초과가 나서 다른 사람의 풀이를 봤더니
sys.setrecursionlimit(재귀 깊이 제한) 을 해주지 않아서 시간초과가 발생한걸 알게 되었다.