[파이썬] 카카오2023 미로 탈출 명령어

응용된 DFS 문제이다.

내 경우에 중요했던 첫번째 포인트는 문제에서 DFS를 수행하는 경우가 두 가지 경우로 나누어진다는 점.
그리고 두 번째 포인트는 불가능한 case를 정확히 찾는 것이다.

기본적으로 이문제는 for 문 수행순서를 d l r u 네 가지를 정확하게 표현해야 한다.
그리고 k 가 실제 거리보다 여유있는 경우에 여유 있게 돌다가 들어가야하는데, 너무 멀리 돌아가면 문제가 생기기 때문에 dist라는 array를 미리 만들어둔다.

dist = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            dist[i][j] = abs(j-c+1) + abs(i-r+1)

1. for문이 순서를 가지고 있는 상태에서 dfs를 가지의 경우에만 수행한다.

1. 현재 위치에서 k 가 여유있게 남아있다면 dfs를 진행한다. `dist[x-1][y-1] < k`
2. 다음 위치를 보았을 때 도착점 까지의 거리가 dist에 표현한 최소 요구거리와 같다면 dfs를 진행한다.` dist[nx-1][ny-1] == k-1:`

종료 조건은 x==r and y==c and k==0: 이다.

2. 불가능 'impossible' 조건을 잘 찾는다.

쉽게 생각할 수 있는 것은 짝, 홀 수를 파악하여 최단거리와 k 의 차이가 홀수가 되지 않게 하는 것이다.
두 번째는 끝까지 고생했는데, k가 직선거리보다 짧게 주어지는 경우이다. (이런 경우가 있을거라는 생각을 하기 어려웠다.)

제출 코드

import sys
sys.setrecursionlimit(2506)
def solution(n, m, x, y, r, c, k):
    if (k - (abs(x-r) + abs(y-c))) % 2:
        return "impossible"
    if k < (abs(x-r) + abs(y-c)):
        return "impossible"
    dist = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            dist[i][j] = abs(j-c+1) + abs(i-r+1)
    
    dx = [1,0,0,-1]
    dy = [0,-1,1,0]
    dict = {0:'d',1:'l',2:'r',3:'u'} 
    answer  = []
    def dfs(x,y,r,c,k):
        if x==r and y==c and k==0:
            return
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
        
            if nx<=0 or nx > n or  ny<=0 or ny > m:
                continue
            elif dist[x-1][y-1] < k or dist[nx-1][ny-1] == k-1:
                answer.append(dict[i])
                return dfs(nx,ny,r,c, k-1)

               
    dfs(x,y,r,c,k)

    return ''.join(answer)