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

---

1. 코드

import sys

sys.setrecursionlimit(100000)
def solution(n, m, x, y, r, c, k):
    def dfs(X, Y, idx, path):
        # 백트래킹
        # 1. 이미 답을 구함
        # 2. 현재 좌표에서 END 까지 남은 이동 횟수 + 현재 움직인 횟수 > k
        if flag[0] or abs(X - R) + abs(Y - C) + idx > k:
            return

        if idx == k:
            # ['d', 'l', 'r', 'u'] 순서로 방문하기 때문에
            # 처음 조건을 충족했을 때가 최선의 답이 된다.
            if (X, Y) == (R, C):
                flag[0] = True
                answer.append(path)
            return

        for i in range(4):
            NX = X + dx[i]
            NY = Y + dy[i]
            if 0 <= NX < n and 0 <= NY < m:
                dfs(NX, NY, idx + 1, path + directions[i])

    # TC 31
    z = k - abs(x - r) + abs(y - c)
    if z < 0 or z % 2 != 0:
        return 'impossible'

    flag = [False]
    directions = ['d', 'l', 'r', 'u']
    dx = [1, 0, 0, -1]
    dy = [0, -1, 1, 0]
    R, C = r - 1, c - 1

    answer = []
    dfs(x - 1, y - 1, 0, '')
    if not answer:
        return 'impossible'
    else:
        return answer[0]

2. 후기

DFS를 사용하지만 처음으로 조건을 충족하는 경우만 답이되기 때문에 flag를 사용하여 남은 함수들을 종료하도록 백트래킹 조건을 추가했다.

여러가지 풀이를 찾다가 이런 경우에는 스택을 사용하여 마지막 값만 계속하여 사용하는 풀이를 봤는데 반복문을 사용하여 재귀함수를 사용한 풀이보다 백트래킹 조건이 직관적이었다. 스택 풀이

그리고 TC31에서 자꾸 시간초과가 떠서 처음부터 불가능을 판별하는 코드를 사용했다.