[C++] 프로그래머스(Lv.3) 미로 탈출 명령어(그리디)

 

난이도 :  Lv3 (중)

알고리즘 유형 : 그리디, 휴리스틱

풀이 방법 : 거리 기반으로 사전순으로 탐색 

 

문제 링크

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

프로그래머스

 

 

문제 설명

n x m 격자 내에서 시작 위치 (x, y)에서 목표 위치 (r, c)로 이동해야 합니다.

총 k번 이동해야 하며, 이동할 때 격자 바깥으로 나갈 수 없습니다.

아래, 왼쪽, 오른쪽, 위쪽(d, l, r, u)으로 움직일 수 있고,

목표 지점까지 정확히 k번의 이동으로 도달해야 합니다.

이 문제에서 k번의 이동으로 목표 지점에 도착할 수 없으면 "impossible"을 반환하고,

가능하다면 움직임 경로를 문자열 형태로 반환해야 합니다.

 

접근 방식

1. 최단 거리 계산: 목표 위치까지의 맨해튼 거리를 dist 변수에 저장합니다.
2. 이동 가능 여부 확인:
   • dist > k인 경우, 최단 거리로도 도착할 수 없으므로
     "impossible"을 반환합니다.
     
     
   • (k - dist) % 2 != 0인 경우, k번 이동해서 도달할 수 없는 상태이므로
     "impossible"을 반환합니다.
3. 움직임 최적화:
   • 가능한 한 아래(d)로 먼저 이동하여 목표와의 수직 차이를 줄여갑니다.
   • 좌우 왕복 및 마지막 상향(u) 이동으로 정확히 k번 이동을 채우고
     목표 지점에 도달할 수 있도록 합니다.

 

문자순으로 d, l, r, u 이기 때문에 가능한 d 부터 먼저 이동하고 맨해튼 거리를 갱신하면서
더 내려갈 수 없다면 l, r, u 순으로 갱신하면서 움직이면 끝입니다.

 

아래는 정답이지만 정리가 안된 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 격자의 바깥으로는 나갈 수 없습니다.
// (x, y)에서 (r, c)까지 이동하는 거리가 총 k
// 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와 dist의 홀짝 불일치 시 불가능)
    if (dist > k || (k - dist) % 2 != 0)
        return "impossible";

    // x,y = start
    // r,c = end
    // k = 거리
    // n, m 보드

    // d, l, r, u 순서로 움직이자.
    // 만약 아래로 그냥 내려갈 수 있다면 d
    // 다 내려갔다면 절대 올라오지않기

    // 내려간 상태로 l부터 r까지 왕복
    // 왕복 끝나면 u로 마무리
    // E(7) . . .
    // 6 . S .
    // 3(5) 2(4) 1 .
    // dist(3, 4, 5, 6)
    // k - dist (7, 6, 5, 4)
    // E . S . 
    // 9 . 1 .
    // 8 . 2 .
    // 7 . 3 .
    // 6 5 4 .
    // . . . .

    for (int i = 0; i < k; ++i)
    {
        if (x != n && dist < k - i)
        {
            r - x > 0 ? --dist : ++dist;
            answer += 'd';
            ++x;
        }
        else
        {
            if (dist == k - i)
            {
                --dist;

                if (r - x > 0)
                {

                    answer += 'd';
                    ++x;
                }
                else if (y - c > 0)
                {
                    answer += 'l';
                    --y;
                }
                else if (c - y > 0)
                {
                    answer += 'r';
                    ++y;
                }
                else
                {
                    answer += 'u';
                    ++x;
                }
            }
            else
            {
                if (y != 1)
                {
                    y - c > 0 ? --dist : ++dist;
                    answer += 'l';
                    --y;
                }
                else if (y != m)
                {
                    c - y > 0 ? --dist : ++dist;
                    answer += 'r';
                    ++y;
                }
                else
                {
                    x - r > 0 ? --dist : ++dist;
                    answer += 'u';
                    ++x;
                }
            }
        }
    }


    return answer;
}

 

 

저는 갱신을 값으로 했지만 다른 분의 코드를 보니 x,y 값만 바꾸고
거리를 다시 재는 함수를 만들어 사용했습니다.

그것을 보고 다시 코드를 작성했습니다.

#include <string>
#include <algorithm>

using namespace std;

int getDist(int x, int y, int r, int c)
{
    return abs(x - r) + abs(y - c);
}


string solution(int n, int m, int x, int y, int r, int c, int k) 
{
    string answer = "";
    
    int dist = getDist(x, y, r, c);
    
    if (dist > k || (k - dist) % 2 != 0)
        return "impossible";
    
    
    while(k--)
    {
        if(x < n && getDist(x + 1, y, r, c) <= k) {answer += "d"; ++x;}
        else if(y > 1 && getDist(x, y - 1, r, c) <= k) {answer += "l"; --y;}
        else if(y < m && getDist(x, y + 1, r, c) <= k) {answer += "r"; ++y;}
        else if(x > 1 && getDist(x - 1, y, r, c) <= k) {answer += "u"; --x;}
    }
    return answer;
}