문제 링크
풀이 과정
전체 코드
from collections import deque
def calcDistance(현재행, 현재열, 도착행, 도착열):
return abs(도착행 - 현재행) + abs(도착열 - 현재열)
def solution(세로, 가로, 출발행, 출발열, 도착행, 도착열, 남은_이동거리):
'''
두 번 이상 방문해도 됨 -> 방문 리스트 로직 불필요
무조건 문자열이 사전 순으로 가장 빠른 경로로 탐색 & 이동 거리 k일 때 탐색 종료
- 탐색 우선 순위: d > l > r > u
유망함수
1. 거리 k로 목적지에 도착이 가능한가?
2. k 미만으로 목적지에 도착했을 때, 남은 거리가 짝수인가?
3. 탐색 도중에, 남은 거리로 목적지에 도착이 가능한가?
'''
if calcDistance(출발행, 출발열, 도착행, 도착열) > 남은_이동거리: return 'impossible'
else:
변화량 = [(-1, 0, 'u'), (0, 1, 'r'), (0, -1, 'l'), (1, 0, 'd')] # 상, 우, 좌, 하
큐 = deque()
큐.append((출발행, 출발열, 남은_이동거리, ''))
while 큐:
현재행, 현재열, 남은_이동거리, 문자열 = 큐.pop() # 최대한 남은 이동거리가 짧은 것부터 탐색하기 위함
if (현재행 == 도착행) and (현재열 == 도착열):
if 남은_이동거리 == 0: return 문자열
elif 남은_이동거리 % 2 == 1: return 'impossible'
for 변화 in 변화량: # popleft()가 아닌 pop()이므로, 큐에 탐색 순서를 역순으로 저장해야 함
다음행 = 현재행 + 변화[0]
다음열 = 현재열 + 변화[1]
if (다음행 >= 1 and 다음행 <= 세로) and (다음열 >= 1 and 다음열 <= 가로):
# 남은 이동거리 안에 목적지까지 갈 수 있는 경우만 탐색 대상에 추가
if calcDistance(다음행, 다음열, 도착행, 도착열) <= 남은_이동거리:
큐.append((다음행, 다음열, 남은_이동거리-1, 문자열+변화[-1]))
return 'impossible'
Python
복사