[프로그래머스 lv3] 미로 탈출 명령어

문제 설명

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

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

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

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

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

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

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

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 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

---

입출력 예nmxyrckresult

3	4	2	3	3	1	5	"dllrl"
2	2	1	1	2	2	2	"dr"
3	3	1	2	3	3	4	"impossible"

 

---

입출력 예 설명

입출력 예 #1

문제 예시와 동일합니다.

입출력 예 #2

미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

S.
.E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

1. rd
2. dr

"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

입출력 예 #3

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

.S.
...
..E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

따라서 "impossible"을 return 해야 합니다.

---

풀이

일단 도착이 불가능한 경우부터 제외시켜 보자.

• 최단거리보다 k가 작으면 도착이 불가능하다.(당연하게도)
• 최단거리보다 k가 크지만 'k-최단거리', 즉 잉여 이동거리가 홀수이면 도착이 불가능하다. 

첫 번째 경우는 당연하지만, 두 번째 경우는 조금 생각이 필요할 수도 있다. 두 번째 경우가 불가능한 이유는, 잉여 이동거리 동안 다른 지점으로 갔다가 다시 올바른 경로로 돌아와야 하는데, 이 다른 지점으로 갔다가 다시 돌아오는 거리는 무조건 짝수이기 때문이다. 

 

그럼 이제 도착이 가능한 경우를 생각해보자.

우선 움직이는 방향의 우선순위가 있다. 알파벳의 먼저 오는 순서로, 아래(d) > 왼쪽(l) > 오른쪽(r) > 위(u) 순이다.

 

도착이 가능한 경우, 일단 현재 지점에서 도착지까지 여유있는 상황인지, 최단거리로 이동해야 하는 상황인지 파악한다.

 

여유있는 상황일 경우, 내 마음대로 움직여도 된다.

그러나 우리는 알파벳 순으로 가장 먼저 오는 경로를 찾아야 하기 때문에, 방향의 우선순위에 따라 해당 방향으로 이동 가능한지 체크한다.

이동 가능한 상태라면 해당 방향으로 이동하고, 아니라면 그 다음 순위의 방향으로 이동 가능한지 체크한다.

다시 말하자면, 아래로 움직일 수 있는 상태면 일단 아래로 움직이고, 아니면 왼쪽, 왼쪽도 안되면 오른쪽, 오른쪽도 안되면 위쪽으로 움직이라는 말이다.

 

여유가 없는 상황일 경우, 최단 거리로 이동해야 하는데, 이 때도 우선순위에 따라 움직인다.

예를 들어, 도착지가 현재 위치의 오른쪽 위에 있다면, 우선순위에 따라 오른쪽으로 먼저 쭉 이동하고 그 다음 위쪽으로 쭉 이동하면 된다. 

---

코드

#include <string>
#include <vector>
#include <stdlib.h>
#include <iostream>
using namespace std;

//최단거리 = K인 경우 : 최단거리로 이동하고 알파벳 순으로 정렬
//최단거리 > K인 경우 : 불가능
//최단거리 < K인 경우 : 쓸데없이 움직여야함.
//ㄴ남는 거리가 홀수다 : 불가능
//ㄴ남는 거리가 짝수다 : 왔다갔다 해야함.
//ㄴㄴ왔다갔다 할 수 있는 공간 체크. d > l > r > u 순으로.

int GetDist(int row1,int col1, int row2, int col2)
{
    return abs(row2-row1) + abs(col2-col1);
}
void MoveDown(int& r, int& c, string& ans)
{
    r +=1;
    ans += 'd';
    cout << "move down"<<endl;
}
void MoveUp(int& r, int& c, string& ans)
{
    r-=1;
    ans += 'u';
    cout << "move up"<<endl;
}
void MoveLeft(int& r, int& c, string& ans)
{
    c-=1;
    ans += 'l';
    cout << "move left"<<endl;
}
void MoveRight(int& r, int& c, string& ans)
{
    c+=1;
    ans += 'r';    
    cout << "move right"<<endl;
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    int minDist = GetDist(x,y,r,c);
    if(minDist > k)
        return "impossible";
    
    if(minDist < k)
    {
        int surplusDist = k - minDist;
        if(surplusDist%2 != 0)
            return "impossible";
    }
    
    int remainMove = k;
    int curR =x,curC=y;

        
    while(remainMove > 0)//k번 움직이기
    {
        int dist = GetDist(curR,curC,r,c);
        cout << "dist: "<<dist<<endl;
        if(remainMove == dist)//이제 진짜 직진해야함
        {
            int rDist = r-curR;
            int cDist = c-curC;
            remainMove--;
            if(rDist > 0)//아래로 가야함
                MoveDown(curR,curC,answer);
            else if(cDist < 0)//왼으로 가야함
                MoveLeft(curR,curC,answer);
            else if(cDist > 0)//오른으로 가야함
                MoveRight(curR,curC,answer);
            else if(rDist < 0)//위로 가야함
                MoveUp(curR,curC,answer);                             
        }else//여유 있음
        {
            remainMove--;
            if(curR != n)
                MoveDown(curR,curC,answer);
            else if(curC != 1)
                MoveLeft(curR,curC,answer);
            else if(curC != m)
                MoveRight(curR,curC,answer);
            else if(curR != 1)
                MoveUp(curR,curC,answer);
        }

    }

    
    return answer;
}