[프로그래머스]Lv3. 미로 탈출 명령어(Python)

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

프로그래머스

 

문제 접근

 

(x, y)에서 (r, c)까지 이동하는 거리가 총 k인 경로 중 사전 순으로 가장 빠른 경로 구하기 

 

<조건>

1. 격자의 바깥으로는 나갈 수 x
2. 같은 격자를 두 번 이상 방문 가능함 
3. S, E는 다름 
4. 해당하는 경로가 없다면 impossible 반환 

---

 

여러 풀이 중에서 해당 문제를 그리디로 접근한 풀이를 참고해서 정리해 보았다. 

                                                                                       ('d') + ('l') + ('rl') + ('r') + ('u')

 

1. 가능한 만큼 아래로 이동 (d)

2. 가능한 만큼 왼쪽으로 이동 (l)

3. 남은 여유 횟수만큼 우좌 이동 반복 (rl)

4. c까지 이동하기 위해 오른쪽으로 다시 이동 (r)

5. r까지 이동하기 위해 위쪽으로 다시 이동 (u)

 

문제의 해를 일반화해보면 위의 경우가 사전적으로 제일 앞에 위치하는 경우가 된다.

 

그렇다면 해당하는 경로가 없는 경우는?

1. 최소 거리 > 가능한 이동 거리(k)

2. 이동 횟수와 맨해튼 거리의 홀짝성이 다른 경우

 

코드 

from collections import defaultdict # 값이 바로 0으로 초기화, 값을 바로 누적 가능 

def solution(n, m, x, y, r, c, k):
    if (abs(x-r) + abs(y-c)) % 2 != k % 2 or abs(x-r) + abs(y-c) > k :  # 경로가 없는 경우 
        return "impossible"
    
    # 필수적으로 이동해야하는 거리 계산 
    essential_x = x-r   # 현재 위치와 목표 위치까지의 차이(상하)
    essential_y = y-c   # (좌우)
    # 남은 이동 거리 계산 
    left = k - abs(essential_x) - abs(essential_y)
    
    word_dict = defaultdict(int)
    
    # 필수 이동 거리에 따라 상하좌우 이동 횟수 계산 
    if essential_x > 0 :    # 현재 위치가 목표 위치보다 아래
        word_dict['u'] += essential_x   # 위로 이동
    elif essential_x < 0 :
        word_dict['d'] -= essential_x
    if essential_y > 0 :    # 현재 위치가 목표 위치보다 왼쪽
        word_dict['l'] += essential_y
    elif essential_y < 0 :
        word_dict['r'] -= essential_y
        
    word_dict['d'] += left // 2
    word_dict['u'] += left // 2
    
    # 가능한 아래로 이동 
    answer = 'd'*min(n-x, word_dict['d'])
    
    if word_dict['d'] - n + x > 0 : # 모든 'd'이동을 사용하지 못했다면 
        # 좌, 우 이동에 배분
        word_dict['l'] += word_dict['d'] - n + x
        word_dict['r'] += word_dict['d'] - n + x
        word_dict['u'] = n - r  # 남은 'u'이동 업데이트
    
    # 가능한 왼쪽으로 이동
    answer += 'l'*min(y-1, word_dict['l'])
    
    if word_dict['l'] - y + 1 > 0 : # 모든 'l'이동을 사용하지 못한다면
        word_dict['l'] -= y - 1
        # 남은 'l'이동을 'rl' 조합으로 대체 
        answer += 'rl' * word_dict['l'] + 'r' * (word_dict['r'] - word_dict['l'])
    else :
        answer += 'r'*word_dict['r']    # 남은 'r'이동 추가 
    
    # 마지막은 'u'로 이동
    answer += 'u' * word_dict['u']
        
        
    return answer

 

 

참고

https://magentino.tistory.com/65

[프로그래머스] 미로 탈출 명령어 (Python)