프로그래머스 - 미로 탈출 명령어

처음 했던 접근

1. 격자를 벗어나지만 않으면 되고, 중간에 벽은 세워져 있지 않으므로 S와 E 사이 거리는 해밀턴 거리로 설정할 수 있다.
2. k와 관계없이, S에서 E로가는 최단 경로에 필요한 알파벳은 모두 정답에 포함될 수 밖에 없다.
3. 또한, E지점에 도달해야 하기 때문에, 정답 문자열은 (S에서 E로가는 문자열에 포함된 알파벳) + (u, d 혹은 l, r 쌍 x개)로 만들 수 있는 문자열 중, 사전순으로 가장 앞에 오는 문자열이다(단, 격자를 넘어가선 안됨)
4. 따라서, S에서 E로가는 최단거리가 짝수이면, k는 짝수여야 하고, S에서 E로가는 최단거리가 홀수이면 k도 홀수여야 한다. 그렇지 않으면 "impossible"을 리턴해야 한다.

(u, d) 쌍, (l, r)쌍을 각각 몇개 넣어야 하는지도 알기 어려웠고, 설사 알아낸다 하더라도 단순 사전순 정렬을 해 버리면 격자를 벗어나는 경우가 생길 수도 있어 해당 케이스를 모두 걸러내야 했다.

여기까지 생각이 도달했을 즈음에 지금 하고 있는 접근이 좋지 못하다는 판단이 들었고, 다른 풀이방법을 생각했다.

정답을 맞춘 접근

1. 문자열이 사전순으로 가장 앞에 와야 하므로, 일단 사전순으로 앞에 있는 알파벳이 최대한 앞으로 와야 한다.
2. 일단 (d > l > r > u) 우선순위로 한칸 이동하고 k를 1만큼 감소시킨다. 이동 후의 지점에서 여전히 E 지점에 도달할 수 있다면(현재 위치와 E지점의 위치의 해밀턴 거리가 k보다 작거나 같으면 현재 위치에서 E지점에 도달 가능하다.) 방금 움직임은 최적의 움직임이다.
   (d로 시작하는 경로는 l, r, u로 시작하는 모든 경로보다 사전순에서 앞선다. 마찬가지로, l로 시작하는 경로는 r, u로 시작하는 경로보다 사전순에서 앞선다.)

여기까지 생각이 닿았을 때 이 문제가 그리디라는 것을 눈치챘고, 답을 맞출 수 있는 알고리즘을 떠올릴 수 있었다.

• 0 : K - (S->E까지 해밀턴 거리)는 양수여야하고, 짝수여야 한다. 그렇지 않으면 "impossible" 리턴.
• 1 : answer = "", 현재 위치를 S로 설정.
• 2 : 현재 위치에서 E까지의 해밀턴 거리가 k와 같은지 비교한다.
• 3-1 : 만약 같다면, answer에 현재위치에서 E까지 가는 사전순으로 가장 앞에오는 최단경로를 append하고 answer를 리턴한다.
• 3-2 : 같지 않다면 일단 (d > l > r > u) 우선순위로 무조건 한칸 이동한다.(격자를 벗어나지 않는 범위에서)
• 4 : 2로 돌아간다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

string answer = "";

int dy[4] = {1, 0, 0, -1};
int dx[4] = {0, -1, 1, 0};
char character[4] = {'d', 'l', 'r', 'u'};

bool isLast(int x, int y, int r, int c, int k) {
    return (k - (abs(x - c) + abs(y - r))) == 0;
}

string getShortestStr(int x, int y, int r, int c)
{
    string ret = "";
    int diffX = c - x;
    int diffY = r - y;
    if(diffY > 0)
    {
        for(int i = 0; i < diffY; i++) 
            ret += 'd';
    }
    if(diffX < 0)
    {
        for(int i = 0; i < (-1) * diffX; i++) 
            ret += 'l';
    }
    if(diffX > 0)
    {
        for(int i = 0; i < diffX; i++) 
            ret += 'r';
    }
    if(diffY < 0)
    {
        for(int i = 0; i < (-1) * diffY; i++) 
            ret += 'u';
    }
    return ret;
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    x--; y--; r--; c--;
    int dist = abs(x - c) + abs(y - r);
    if(k < dist || (k - dist) % 2 == 1) return "impossible";
    
    int curX = y;
    int curY = x;
    
    while(1)
    {
        if(isLast(curX, curY, r, c, k))
        {
            answer += getShortestStr(curX, curY, r, c);
            break;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int ny = curY + dy[i];
            int nx = curX + dx[i];
            if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            
            answer += character[i];
            curX = nx;
            curY = ny;
            k--;
            break;
        }
    }
    return answer;
}