미로 탈출 명령어

⭐️
import sys
sys.setrecursionlimit(10**8)

N, M, R, C, K = -1, -1, -1, -1, -1
answer = ""

# d, l, r, u
dx, dy = [1, 0, 0, -1], [0, -1, 1, 0]
direction = ["d", "l", "r", "u"]

def dfs(cx, cy, cnt, res):
    global answer
    
    # (지금까지 온 거리 + 남은거리) 가 K보다 크다면 이미 실패
    if K < cnt + abs(cx - R) + abs(cy - C):
        return
    
    # 조건 부합
    if cx == R and cy == C and cnt == K:
        answer = res
        return
    
    for idx, (dxx, dyy) in enumerate(zip(dx, dy)):
        nx, ny = cx+dxx, cy+dyy
        if 1 <= nx <= N and 1 <= ny <= M and res < answer:
            dfs(nx, ny, cnt+1, res+direction[idx])
    


def solution(n, m, x, y, r, c, k):
    global N, M, R, C, K, answer
    N, M, R, C, K = n, m, r, c, k
    answer = "z"*N
    
    # k 자체가 최단거리보다 작거나
    # (k-최단거리) == 홀수 일경우 다시 돌아올 수 X
    dist = abs(x - r) + abs(y - c)
    if dist > k or (k - dist) % 2 == 1:
        return "impossible"
    
    dfs(x, y, 0, "")
    
    return answer

2023 KAKAO BLIND RECRUITMENT

풀면서 특이했던 점은 왔던 길을 또 가도 상관없다, 즉 visited 배열이 소용이 없다는 것.
따라서, bfs 를 쓰기 애매해진다.
왜냐하면 visited 배열을 체크를 안해주면서 bfs를 돌리면 그 경우의 수가 정말 너무 많아지기 때문이다.

문제에서도 답을 String의 알파벳 순으로 가장 앞선 것을 원했으므로 차라리 dfs 로 깊게 탐색하는 것이 나아 보인다.

여기서 최적화를 생각해야 하는 것은 k와 최단거리 사이의 비교 인데,
K가 이미 최단거리(행 차이 + 열 차이) 보다 작다면 절대 불가능.
또한 (K-최단거리) 가 홀수라면 왔다갔다가 불가능하기 때문에 도착점에 정확히 멈출 수가 없다. 따라서 절대 불가능.

이 처리를 하고서 dfs 로직을 짜면 그 다음은 간단했다.

한 가지 갸웃했던 점은 이렇게 dfs로 짜면 깊이가 깊어질 것 같다는 점이다.
그래서 시간초과가 나면 어떡하나 걱정했는데 역시...
근데 sys 에서 직접 setRecursionlimit, 즉 recursion depth 를 조절해주면 바로 통과하긴 한다.
하지만 코테에서 dfs를 돌리고 시간초과가 나면 다른 방법을 생각해보지 수동으로 recursion 을 조절할 생각을 하긴 힘들 것 같은데..

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