프로그래머스 Lv.3 [2023 KAKAO BLIND RECRUITMENT] 미로 탈출 명령어 Python

문제 링크 : https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&partIds=37527 

코딩테스트 연습 | 프로그래머스 스쿨

정답 코드

import sys
sys.setrecursionlimit(10**9)

result = "z"

def solution(n, m, x, y, r, c, k):
    dist = abs(x - r) + abs(y - c)
    if dist > k or (k - dist) % 2 == 1:
        return "impossible"
    
    def isValid(nr, nc):
        return 1 <= nr <= n and 1 <= nc <= m

    def dfs(sr, sc, res):
        global result
        if res > result:
            return
        if len(res) + abs(sr-r) + abs(sc-c) > k:
            return
        if (sr, sc) == (r, c) and len(res) == k:
            result = res
            return
        
        for dr, dc, dd in ((1, 0, "d"), (0, -1, "l"), (0, 1, "r"), (-1, 0, "u")):
            nr = sr + dr
            nc = sc + dc
            ns = res + dd
            if isValid(nr, nc) and res < result:
                dfs(nr, nc, ns)
    dfs(x, y, "")
    return result

핵심 부분

if len(res) + abs(sr-r) + abs(sc-c) > k:
	return

느낀점

 아무리 문제를 잘 풀었다고 하더라도 시간복잡도에 대한 개념이 부족할 경우 쉬운 문제도 오래 걸리게 된다. 문제 푸는 것 까지는 좋았는데 가지치기 부분에서 조금 어려웠다. 이번 가지치기는 움직인 거리와 움직여야 하는 거리(현재 지점부터 도착 지점까지의 거리)가 k(총 움직여야 하는 거리)보다 큰 경우 return해야 한다. 거리에 대한 개념이 부족했을뿐더러 오랜만에 dfs문제를 풀어서 더욱 찾기 어려운 부분이었다.