23.05.11 파이썬 코딩 퀴즈#241 미로 탈출 명령어 (프로그래머스 스쿨)

이번 문제는 미로탈출 명령어 문제이다.

기존의 미로 문제에서 조금 변형된, 조금은 더 어려운 문제이다.

먼저 미로를 탈출하기 위한 조건이 기존 문제와는 틀리다.

1. 격자(nxm) 밖으로는 이동할 수 없다.

2. 시작위치 (x,y)에서 (r,c)까지 이동하는 거리는 총 k 여야 하며, 모든 격자를 두 번 이상 방문 가능하다.

3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출 해야 한다.

 

문자열 'lul'은 왼쪽(left) 한칸, 위(up) 한칸, 왼쪽(left) 한칸을 움직였음을 의미한다.

위 경우를 코드로 확인해보면, 정확히 34가지의 탈출 명령어가 나오게 되며, 이 중 사전 순으로 가장 빠른것은 'dllrl' 이 된다.

총 7개의 변수가 주어지지만, 정리해보면

미로의 크기를 나타내는 n x m

시작위치 x, y, 탈출 지점 r, c 그리고 탈출에 필요한 이동거리 k 로 정리 가능하다.

만약 위 조건대로 미로를 탈출 할 수 없는 경우라면 'impossible'을 return 해야 한다.

탈출이 불가능한 입출력 예 3번을 살펴보자.

탈출이 가능한 경로가 여러가지가 보이는데, 그 중 'rdd', 'drd', 'lddrr' 세가지가 눈에 띈다.

'lddrr'의 경우는 k(4) 보다 크기 때문에 탈락이고, 그렇다면 두개만 살펴보며 되는데

둘다 최단거리 이지만 k(4)보다 1 부족하다. 통과를 위해서는 2의 배수(좌우 또는 상하 반복이동) 만큼 k보다 작아야 하지만, 위 경우는 남은 거리가 1 이기 때문에 불가능하다.

 

코드를 작성하던 도중에 한가지 의문점이 생겼다.

만약 최단거리를 탈출하는 코드가 'rru' 이고, k 가 5라면?

굳이 최단거리로 탈출하는 것보다는 사전순 우선순위에 의해 'lr'을 먼저 실행하고 'rru'를 실행하면, 'rru'로 도착 이후에 움직이는 것보다 사전순으로 더 빠른 'lrrru'가 나오게 된다.

즉 최단거리를 우선시 하는 코드는 해당 문제를 올바르게 풀 수 없다.

 

먼저 문제 설명에서 힌트를 얻어야 한다.

해당 문제의 정답은 '사전순'으로 k 만큼 이동하여 도달 가능한 명령어이다.

즉 아래 (d) 가 최우선 이동 경로이고, 그 다음은 왼쪽(l), 오른쪽(r), 위(u) 순서이다.

즉 처음 시작 위치에서 아래로 가는 경로가 존재한다면 굳이 다른 경로를 선택할 이유가 없다.

 

그렇다면 그 다음 경로는 어떻게 선택해야 할까?

정답은 이동할 위치에서 목표까지의 거리를 계산하고, 계산된 값이 k 이하라면 이동 가능한 방향이 된다.

입출력 예를 다시 생각해보자.

우선 이동 방향은 아래(d)가 된다. 그 다음 우측 또는 좌측, 위쪽으로 이동 가능하지만 사전순 우선 순위에 따라 무조건 왼쪽(l)을 선택하고, 그 다음도 왼쪽(l)을 선택하게 된다.

이제 목표에 도달하였고 현재 위치에서 그 다음 이동 가능한 위치는 위, 오른쪽 이다. 사전순에 의해 위쪽은 버리고 오른쪽만 택하여 이동 가능하다.

그 다음 다시 남은 이동 횟수를 고려하여 오른쪽으로 더 이동은 불가하고, 다시 왼쪽으로 이동하여 남은 탈출 명령어를 채워주게 된다.

 

위 코드의 다음 위치로 이동 가능할 때, 남은 횟수를 고려하여 왼쪽으로 이동이 가능하다면 무조건 왼쪽을 먼저 선택하게 하여 사전순으로 우선순위를 만드는 것에 있다.