[프로그래머스/C++] 미로 탈출 명령어 (2023 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 미로를 통과하기 위한 여러 경로 중 오름차순으로 가장 빠른 경로를 return하면 되는 문제다.

 

먼저 정확히 k번을 움직여 그 도착점에 도달해야하기 때문에 도달이 가능한지 판단하는 것도 중요하다.

만약 위 그림처럼 시작점과 목적지가 주어졌다면, 시작점에서 목적지로 도달하기 위해서는 짝수 번 움직여야한다.

 

왜냐하면 도착지점과 시작지점의 거리가 3+3 = 6으로 짝수이기 때문이다.

만약 k가 홀수라면 어떤 방법을 써도 도달할 수 없다.

 

이유는 쉽게 생각할 수도 있지만, 굳이 수식을 써서 증명을 해보면

 

먼저 s의 좌표를 sx, sy라고 하자

이제 상하좌우로 움직이는 횟수를 a, b, c, d로 표현하면 이동 후 좌표는 (sx+a-b), (sy+c-d)와 같다.

이제 이동 후 x, y좌표를 더한 값을 Sum = sx + sy + a - b + c - d 로 표현하면, 여기서 a+b+c+d=k이므로

 

Sum + k = sx + sy + 2(a + c), Sum = sx + sy + 2(a+c) - k 가 된다.

여기서 2(a+c)는 항상 짝수이므로 Sum을 2로 나눈 값은 k에만 영향을 받는다.

 

그러므로 시작좌표의 합 + k를 2로 나눈 값이 도착좌표를 2로 나눈 값과 같아야 한다는 결론이 나온다.

  

그러므로 목적지에 도착이 가능한 조건은 아래와 같다.

 

1. 시작좌표의 합 + k를 2로 나눈 값이 도착좌표의 합을 2로 나눈 값과 같아야 한다

2. 도착지와 출발지의 사이의 거리가 k보다 작거나 같아야 한다.

 

이 조건을 만족하지 않으면 불가능한 경우다.

 

경로를 검사하는 방법은 훨씬 쉽다.

사전순으로 빠른 경로를 얻어야 하므로 항상 dlru 순서로 이동이 가능한지 체크하고 이동이 가능하다면, 이동하면 된다.

 

여기서 이동이 가능한지 체크하는 사항은 두 가지다.

1. 이동했을 때, 격자의 범위를 벗어나지 않는다.

2. 이동후에도 현재 위치와 도착지의 거리가 남은 이동횟수보다 크거나 같을 것

 

위 두 조건을 체크하고 이동이 가능하다면 바로 이동하면 된다.

dlru 순서로 검사를 하기 때문에 이동이 가능하다면 바로 break하고 다음에 이동할 경로를 체크하면 된다.

 

+ 최소 횟수로 이동 후 좌표가 목적지와 다를 경우 impossible을 return하는 방법도 있다.

 

 

[아이디어 정리]

1. 시작점에서 목적지에 도달할 수 있는지 체크하고 이동이 불가능하면 impossible을 return한다.
2. 현재 위치에서 다음 좌표로 이동이 가능한지 dlru순서로 체크하고 이동이 가능하다면 이동하고 break한다.
3. 최종적으로 저장된 경로를 return한다.

 

 

Code (사전 체크)

 

 

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

//dlru 순서
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};


string solution(int n, int m, int x, int y, int r, int c, int k) {
    if (((abs(x-r)+abs(y-c))%2!=k%2)||(abs(x-r)+abs(y-c)>k))
    {
        return "impossible";
    }
    else
    {
        string retA="";
        string cc="dlru";
        int ny,nx;
        while(k>0)
        {
            k--;
            for (int i=0; i<4; i++)
            {
                ny=y+dy[i];
                nx=x+dx[i];
                if (abs(nx-r)+abs(ny-c)<=k&&ny>=1&&ny<=m&&nx>=1&&nx<=n)
                {
                    retA+=cc[i];
                    y=ny;
                    x=nx;
                    break;
                }
            }    
        }
        return retA;
    }    
}

 

 

 

 

Code2

 

 

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

//dlru 순서
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};


string solution(int n, int m, int x, int y, int r, int c, int k) {
    string retA="";
    string cc="dlru";
    int ny,nx;
    while(k>0)
    {
        k--;
        for (int i=0; i<4; i++)
        {
            ny=y+dy[i];
            nx=x+dx[i];
            if (abs(nx-r)+abs(ny-c)<=k&&ny>=1&&ny<=m&&nx>=1&&nx<=n)
            {
                retA+=cc[i];
                y=ny;
                x=nx;
                break;
            }
        }    
    }
    if (nx!=r||ny!=c)
        return "impossible";
    return retA;
}

 

---

 

처음에 x와 y가 내가 생각한것과 다르게 반대로 설정돼 있어 헷갈렸다.. EZ

 

 

프로그래머스