[프로그래머스]코딩테스트 연습>>2023 KAKAO BLIND RECRUITMENT>>미로 탈출 명령어

• 미로 탈출 명령어

문제 설명

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

---

제한사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

---

입출력 예nmxyrckresult

3	4	2	3	3	1	5	"dllrl"
2	2	1	1	2	2	2	"dr"
3	3	1	2	3	3	4	"impossible"

---

입출력 예 설명

입출력 예 #1

문제 예시와 동일합니다.

입출력 예 #2

미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

S.
.E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

1. rd
2. dr

"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

입출력 예 #3

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

.S.
...
..E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

따라서 "impossible"을 return 해야 합니다.

 

 

 

#include<bits/stdc++.h>

using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1},d,u,r,l;
string answer;
int cal(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) {
    int down=r-x;int right=c-y;
    if((k-cal(x,y,r,c))%2 !=0 || k<cal(x,y,r,c)) return "impossible"; //이동후 ,짝수횟수만큼 이동거리가 남아야함
    //목적지가 아래면 down은 양수
    while(1){
      int dist=cal(x,y,r,c);
        if(k==dist){
            while(x<r){
                answer.push_back('d');
                x++;
            }
            while(y>c){
                answer.push_back('l');
                y--;
            }
            while(y<c){
                answer.push_back('r');
                y++;
            }
            while(x>r){
                answer.push_back('u');
                x--;
            }
            break;
        }//남은 이동가능 수와, 거리가 같으면 >> 최적화됨 dlru순서대로 출력후 반환 끝
        if(x+1 <= n){ //범위내 아래로 이동가능
            x++; //이동
            k--;
            answer.push_back('d');
            continue;
        }
        if(x+1>n){ //이동가능거리가 더 긴데 아래로 더이상 못가
            if(y-1>=1){//왼쪽으로 이동가능
                y--;
                k--;
                answer.push_back('l');
                continue;
            }
            else if(y+1<=m){
                y++;
                k--;
                answer.push_back('r');
                continue;
            }
        }
        if(x-1>=1){
            x--;
            k--;
            answer.push_back('u');
            continue;
        }
    }
    return answer;
}

문제를 처음 봤을때는 백트래킹을 생각했습니다.

5회 이동시 목적지에 위치해있다면 정답을 갱신합니다.

하지만 뻔하게 시간초과...

 

BFS+백트래킹을 이용해서

현재 위치에서 목적지까지 최단거리 > 남은 이동가능 거리 인 경우 가지치기를 해주었지만 마찬가지로 

시간초과.....

 

아무래도 2500*2500칸에 백트래킹은 말이 안되는것 같아서

BFS가 아니라, 그리디하게 접근했습니다.

 

이동 방향의 우선순위는 D R  L U 로,  아래,오른,왼,위 입니다.

사전순으로 가장 빠른 경우를 출력해야하므로, 아래쪽으로 최대한 움직일 수 있을만큼 움직이고, 왼쪽으로 마찬가지 오른쪽으로 마찬가지 그다음 위로 움직이면 됩니다.

 

현재 위치를 기준으로 목적지까지 이동해도 거리가 남아있는 상황이 문제입니다. 따라서,

현재위치를 기준으로 목적지까지 최단거리가 남을 때 까지 그리디하게 움직일 것입니다.

 

1. 최단거리와 이동가능거리가 남아있다면

1-1. 아래로 움직일 수 있을만큼 움직입니다.

1-2. 왼쪽으로 움직일 수 있을만큼 움직입니다.

1-3. 오른쪽으로 수행

1-4. 위로 수행

 

2.만약 최단거리와 이동가능거리가 같다면

1-1. 목적지가 아래에 있다면 아래로 움직입니다.

1-2. 목적지가 왼쪽에 있다면 왼쪽으로 움직입니다

1-3. 목적지가 오른쪽에 있다면 오른쪽으로 움직입니다.

1-4.목적지가 위에 있다면 위로 움직입니다.