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

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

프로그래머스

Status : Solved

Time : 01:08:08

 

---

 

문제 설명

 

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

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

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

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

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

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

* 문제 예시는 위쪽 링크를 참조해주세요!

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

 

입력 및 출력

 

제한사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

 

입출력 예

n	m	x	y	r	c	k	result
3	4	2	3	3	1	5	"dllrl"
2	2	1	1	2	2	2	"dr"
3	3	1	2	3	3	4	"impossible"

 

 

---

 

풀이

대망의 5번 문제. 카카오 코테 도중에, 이 문제에서 약간의 시행착오를 겪은 바 있어 더 꼼꼼하게 풀었던 것 같다. 예전에 문제를 풀 때는 '경우의 수를 가지치기하고 남은 경우의 수 중 조건을 만족하는 최적해를 찾는' 방식으로 도전했었는데, 거의 시간 초과에 가까웠었다. 모든 조합을 검사하는 것은 그만큼 비효율적이다.

하지만 2번째로 마주했을 때, 이 문제는 그리디한 접근이 가능하다는 걸 깨달아 그 쪽으로 문제를 풀이해본다. 요약하면 "탐색문제인 척 하는 그리디 문제"라고 할 수 있겠다. 막상 풀이하려니 알고리즘을 구체화하는 데 시간이 많이 걸려 1시간이 넘어갔다는 건 비밀이다.

우선 불가능한 경우는 k와 출발지-목적지 간의 거리를 2로 나눈 나머지가 다를 때이다. 한쪽이 짝수, 다른 쪽이 홀수인 경우는 어떤 조합으로든 도착할 수 없다. 또한 최소 거리보다 가능한 이동거리 k가 작을 경우 역시 불가능하다.

잘 생각해보면, 이 문제의 해는 다음과 같은 꼴로 나타나게 된다 :

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

1. 가능한 만큼 아래로 이동하고
2. 가능한 만큼 왼쪽으로 이동한 후
3. 남은 여유분만큼 우좌 이동을 반복한 후
4. 목적 좌표 c까지 이동하기 위해 오른쪽으로 다시 이동하고
5. 목적 좌표 r까지 이동하기 위해 위쪽으로 다시 이동하는

형태를 띄어야 한다. 이 경우가 사전적으로 제일 앞에 오는 경우가 된다. 이를 구체화하는 게 핵심이 된다.

1. 원래 상하 이동 거리과 좌우 이동은 출발지-목적지 간의 x좌표와 y좌표의 차로 구할 수 있다.
2. 남는 잉여 거리는 이러한 출발지-목적지 간 최소거리와 목표 이동거리 k의 차이다. 즉 남는 잉여 거리의 배분이 핵심이 된다.
3. 원래 아래쪽 이동 거리를 고려하여 가능한 만큼 아래로 이동하면, 잉여 거리는 그만큼 감소하게 된다.
4. 그리고 감소한 잉여 거리와 원래 왼쪽 이동 거리를 합하여 가능한 만큼 왼쪽으로 이동한다.
5. 남은 왼쪽 이동 거리가 '여유분'이 된다. 만약 이동거리가 있다면 그 '여유분'만큼 우좌 이동을 반복한다('rl')
6. 5번까지 수행했을 때, 다음에는 무조건 목적지로 오른쪽 위로 이동해야 한다. 오른쪽 목적 좌표까지 이동 -> 위쪽 목적 좌표까지 이동으로 마무리하면 된다.

글로 표현하니 더 복잡해보이는데, 코드는 더 더러워져버렸다... 오늘다라 집중력이 많이 저하된 게 이유인듯하다. 다음엔 좀 더 조용한 장소에서 풀어봐야지...

 

풀이 코드

from collections import defaultdict

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 : ### 무조건 left // 2 를 다 못쓴 상황
        word_dict['l'] += word_dict['d'] - n + x
        word_dict['r'] += word_dict['d'] - n + x
        word_dict['u'] = n - r
    
    answer += 'l'*min(y-1, word_dict['l'])
    if word_dict['l'] - y + 1 > 0 :
        word_dict['l'] -= y - 1
        answer += 'rl' * word_dict['l'] + 'r' * (word_dict['r'] - word_dict['l'])
    else :
        answer += 'r'*word_dict['r']
    
    answer += 'u' * word_dict['u']
        
        
    return answer

풀이 완료!