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

프로그래머스 미로 탈출 명령어 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

n x m크기의 격자 미로가 주어지며 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
미로를 탈출하는 조건이 세 가지 있습니다.
1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 l:왼쪽, r:오른쪽, u:위쪽, d:아래쪽와 같은 문자열로 나타낼 수 있으며 문자열로 탈출 경로를 구해야합니다.
단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

문제 풀이

처음 볼 때는 미로찾기 같았지만, 좀 더 생각해보니 주어진 조건대로라면 if문으로 간단하게 만들 수 있었습니다.

일단 사전순으로는 d->l->r->u이므로 최대한 아래->왼쪽->오른쪽->위쪽 순서대로 움직이게 만들게 되면 사전순으로 제일 빠른 경로를 만들 수 있습니다.

처음에 시작점과 도착점의 거리를 계산하여 k값으로 이동이 가능한지 비교해줍니다.
가능하다면 도착점까지와의 거리와 (k-이동한 거리)값이 같아질때까지 사전순으로 제일 빠르도록 이동해줍니다.
아래로 이동할 수 없을 때까지 먼저 아래로 이동하고, 왼쪽으로 움직일 수 없을 때까지 왼쪽으로 이동해줍니다.
아래와 왼쪽의 끝에 다다르면 오른쪽->왼쪽을 반복하며 (k-이동한 거리)값이 같아질 때 까지 반복해줍니다.

이후에 같아지게 된다면 아래->왼쪽->오른쪽->위쪽 순서대로 움직이며 도착지점으로 이동해주면 됩니다.

전체 코드

if문으로 문제를 해결하면 반례에 걸려 불가능할 줄 알았지만 이러한 방법으로 풀어지니 조금 놀랐습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

//d >> l >> r >> u 사전순
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    int dist = abs(x-r) + abs(y-c);
    //만약 도착이 불가능한 k가 주어진다면 return
    if(k-dist < 0 || (k-dist)%2 != 0)
        return "impossible";
    
    for(int i = 0; i < k; i++)
    {
        dist = abs(x-r) + abs(y-c);
        if(dist < k-i) //남은 이동 횟수가 도착지점까지 가는 이동 횟수보다 더 클 경우
        {
            //맨 아래 -> 맨 왼쪽 -> 오른쪽 순으로 움직임
            if(x < n)
            {
                answer = answer + "d";
                x++;
            }else if(y > 1)
            {
                answer = answer + "l";
                y--;
            }else
            {
                answer = answer + "r";
                y++;
            }
        }else
        {
            //아래 -> 왼쪽 -> 오른쪽 -> 위 순서로 도착지점으로 이동
            if(x < r)
            {
                answer = answer + "d";
                x++;
            }else if(y != c)
            {
                if(y < c)
                {
                    answer = answer + "r";
                    y++;
                }else
                {
                    answer = answer + "l";
                    y--;
                }
            }else
            {
                answer = answer + "u";
                x--;
            }
        }
    }
    
    //만약 도착지점이 도착하지 않았을 경우
    if(x != r || y != c)
    {
        answer = "impossible";
    }
    
    return answer;
}

출저

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