[1일 1알고] 미로 탈출 명령어

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

프로그래머스

일반적인 그리디 문제입니다.

k만큼의 이동을 통해서 start에서 end로 도달해야합니다.

 

중간에 장애물도 없기 때문에 거리 계산은 좌표를 통한 맨하탄 거리를 그대로 사용하면 됩니다.

이동이 가능한 경우 중 사전 순 d, l, r, u의 우선순위로 이동해야하기 때문에 이를 고려하면 됩니다.

 

k가 2500이하이며 n, m또한 그에 맞게 50이하이기 때문에 매번 이동을 계산하더라도 전혀 부담이 없을 것입니다.

 

using namespace std;

// nxm 미로
// x, y -> r, c로 가는 길
// 이동 거리가 k여야 하며, 같은 격자를 중복 방문이 가능하다
// 경로를 문자열로 나타냈을 때 사전 순으로 가장 빠른 경로로 탈출이 필요

// l, r, u, d로서 좌우상하를 표현하며, 
// abcd순으로 생각하면 d -> l -> r -> u 순서가 우선순위이다.
// 제자리로 오는 경우 d -> u / l -> r / r -> l / u -> d

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";

    int dist = abs(r - x) + abs(c - y);

    if (dist % 2 != k % 2)
        return "impossible";
    else if (dist > k)
        return "impossible";

    int dr[4] = { 1, 0, 0, -1 };
    int dc[4] = { 0, -1, 1, 0 };

    while (k > 0)
    {
        for (int i = 0; i < 4; ++i)
        {
            int nr = x + dr[i];
            int nc = y + dc[i];
            dist = abs(r - nr) + abs(c - nc);
            if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && dist <= k - 1)
            {
                x = nr;
                y = nc;
                --k;
                switch (i)
                {
                case 0:
                    answer += 'd';
                    break;
                case 1:
                    answer += 'l';
                    break;
                case 2:
                    answer += 'r';
                    break;
                case 3:
                    answer += 'u';
                    break;
                }

                break;
            }
        }
    }

    return answer;
}

코드는 보면 이해가 쉬울 것입니다.

 

이러한 문제 특성상 항상 경계처리 등을 주의해야합니다.

이 문제에서는 1-based좌표이기 때문에 이를 신경써야합니다.