[Python] 프로그래머스 - 2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어

 

프로그래머스

문제 

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 해야 합니다.

 

문제해결방법

 

1. 알파벳이 빠른 순서대로 가면서 주어진 k에 맞는 턴으로 움직여야 한다.

 

1) 우선순위는 'd', 'l', 'r', 'u' 가 된다.

2) 주어진 거리(abs(x-r)+abs(y-c))가 있고, k보다 큰데, 차이가 홀수면 턴수가 안맞아 도달할 수 없다. 짝수의 차이가 있으면 도착하거나 중간에서 '왔다갔다'를 통해서 주어진 도착점(r, c)에 도달할 수 있다.

3) dfs알고리즘으로 동작하는데, len(string)+abs(a-r)+abs(b-c) > k 라면 최소동선이 아니다.

 

- 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m, x, y, r, c, k = [3, 4, 2, 3, 3, 1, 5]

da = [1, 0, 0, -1]
db = [0, -1, 1, 0]
s = ['d', 'l', 'r', 'u']
res = 'z'
dist = abs(x-r)+abs(y-c)

def check(x, y):
	return 1 <= x <= n and 1 <= y <= m

def dfs(a, b, string):
	global res
	if string > res:
		return
	if dist > k or (k-dist) % 2 == 1:
		return 'impossible'
	if len(string)+abs(a-r)+abs(b-c) > k:
		return
	if a == r and b == c and len(string) == k:
		res = string
		return 
	for i in range(4):
		na = a+da[i]
		nb = b+db[i]
		if check(na, nb) and string < res:
			dfs(na, nb, string+s[i])
			
dfs(x, y, '')
print(res)