문제 링크

풀이 과정

전체 코드

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'