문제

programmers.co.kr/learn/courses/30/lessons/150365

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

격자의 바깥으로는 나갈 수 없습니다.
(x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

풀이

탐색 순서

문제에서 주어지는 탈출 지점으로 가는 탈출 경로 중 가장 빠른 순을 원합니다. 방향이 d, l, r, u 순으로 탐색을 시작해야 나머지 경우에 대해서 방문하지 않고 탈출 경로를 찾을 수 있습니다.

탈출 불가능

1. k가 dist(탈출 최단 거리)보다 작을 경우 자명하게 탈출이 불가능합니다.
2. 탈출 지점에 도착 후, 두 번 이동하면 제자리로 돌아올 수 있습니다. 따라서 (k - dist)가 짝수가 되어야 합니다.

(k - dist) % 2 == 1

문자열 비교

파이썬이 강력한 이유가 아닐까 싶습니다. 방문하지 않아도 되는 경로는 탐색하지 않도록 조건을 제한합니다. 가령 이미 dllrl의 경로가 존재할 경우, dl에서 u방향으로 탐색할 필요가 없습니다. 따라서 문자열 비교를 통해서 이를 제한합니다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]
dAlpha = ['d', 'l', 'r', 'u']
answer = "z"


def isVaild(nx, ny, n, m):
    return 1 <= nx and nx <= n and 1 <= ny and ny <= m


def dfs(n, m, x, y, r, c, prev_s, cnt, k):
    global answer
    if k < cnt + abs(x - r) + abs(y - c):
        return
    if x == r and y == c and cnt == k:
        answer = prev_s
        return
    for i in range(4):
        if isVaild(x + dx[i], y + dy[i], n, m) and prev_s < answer:
            dfs(n, m, x + dx[i], y + dy[i], r, c, prev_s+dAlpha[i], cnt + 1, k)


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"

    dfs(n, m, x, y, r, c, "", 0, k)

    return answer