2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어

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

DFS. 스택으로 풀었다. 

방향은 dlru 순으로 확인해야 한다. 

스택은 마지막 입력한 것부터 pop 하기 때문에... 아래 코드와 같은 순서를....

중간에 최소 거리가 남은 거리 보다 큰 경우, 홀짝이 안 맞는 경우는 가지치기를 했다. 

def solution(n, m, x, y, r, c, k):
    stack = [(x, y, [])]
    result = 'impossible'
    while stack:
        x_pos, y_pos, path = stack.pop()
        if len(path) == k and (x_pos, y_pos) == (r, c):
            result = ''.join(path)
            break
        remain, shortest_path = k - len(path), abs(x_pos - r) + abs(y_pos - c)
        if remain < shortest_path or remain % 2 != shortest_path % 2:
            continue
        if x_pos > 1:
            stack.append((x_pos - 1, y_pos, path + ['u']))
        if y_pos < m:
            stack.append((x_pos, y_pos + 1, path + ['r']))
        if y_pos > 1:
            stack.append((x_pos, y_pos - 1, path + ['l']))
        if x_pos < n:
            stack.append((x_pos + 1, y_pos, path + ['d']))
    return result

테스트 1 〉	통과 (0.17ms, 10.2MB)
테스트 2 〉	통과 (0.17ms, 10.2MB)
테스트 3 〉	통과 (0.00ms, 10.4MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.4MB)
테스트 6 〉	통과 (0.02ms, 10.4MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.03ms, 10.2MB)
테스트 9 〉	통과 (73.41ms, 68.9MB)
테스트 10 〉	통과 (73.06ms, 67.4MB)
테스트 11 〉	통과 (74.00ms, 66.9MB)
테스트 12 〉	통과 (72.25ms, 68MB)
테스트 13 〉	통과 (72.01ms, 67.5MB)
테스트 14 〉	통과 (74.58ms, 69.4MB)
테스트 15 〉	통과 (73.52ms, 68.9MB)
테스트 16 〉	통과 (71.45ms, 65.8MB)
테스트 17 〉	통과 (73.01ms, 65.6MB)
테스트 18 〉	통과 (73.60ms, 67MB)
테스트 19 〉	통과 (72.03ms, 67.6MB)
테스트 20 〉	통과 (70.63ms, 65.3MB)
테스트 21 〉	통과 (71.25ms, 65.5MB)
테스트 22 〉	통과 (71.94ms, 66.7MB)
테스트 23 〉	통과 (72.29ms, 67.9MB)
테스트 24 〉	통과 (70.77ms, 67.1MB)
테스트 25 〉	통과 (73.75ms, 66.8MB)
테스트 26 〉	통과 (73.98ms, 67.7MB)
테스트 27 〉	통과 (73.74ms, 66.9MB)
테스트 28 〉	통과 (71.46ms, 65.6MB)
테스트 29 〉	통과 (77.24ms, 69.8MB)
테스트 30 〉	통과 (77.25ms, 69.8MB)
테스트 31 〉	통과 (0.00ms, 10.2MB)