[프로그래머스/Level 3/C++/2023 카카오 블라이드 채용] 미로 탈출 명령어

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

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

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

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

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

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

- 미로의 좌측 상단은 (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

 

[문제 풀이]

프로그래머스에 최근에 올라온 문제 같은데 아직 구글에 풀이가 없어서 한 번 작성해봅니다.

 

만약 문제시 삭제하도록 하겠습니다.

 

문제를 읽고 처음에 접근했던 방식은 다음과 같다. ( 틀린 방법임 )

• S에서 E까지 "아래 , 왼쪽, 오른쪽, 위" 방향 순서대로 DFS를 이용하여 이동한다. ( 한 번 방문한 지점은 다시 방문 x )
• E에서 남은 길이의 절반 만큼 "아래 , 왼쪽, 오른쪽, 위" 방향 순서대로 추가로 이동한 후 반대되는 방향을 문자열에 추가해준다. ( 예를들어 남은 길이가 10일 때, 절반 만큼인 5를 이동할때 d , l , l ,r ,u 로 이동했으면  dllru도 정답 문자열에 추가하고, dlrru을 추가로 정답 문자열에 넣어 준다. ) 

이 방법으로 접근했었는데, 계속 정답이 틀리거나 시간 초과가 나길래 시간을 줄이는 방법으로 접근했었는데, 다른 예제들을 직접 만들어 풀어보니 위 방법으로는 사전순으로 빠른 경로를 찾기가 어려웠다.

 

그래서 다른 방법으로 접근했었는데 방법은 다음과 같다.

• S지점에서 "아래 , 왼쪽, 오른쪽, 위" 방향 순서대로 격자판을 이동한다.
• E지점까지 거리 |x1-x2| +|y1-y2|를 이용하여 남은 거리와 이동 가능한 남은 거리를 비교하여 E까지 갈 거리가 충분하다면 "아래 , 왼쪽, 오른쪽, 위" 방향 순서대로 계속 진행한다. 만약 거리가 부족하면 이동하지 않는다.

무슨 뜻이냐면 격자판에서 이동을 할 때 새로 도착하는 지점에서 E까지의 남은 거리가 이동가능한 횟수보다 크다면 새로 도착하는 지점에서 E까지 도달이 불가능하다. 따라서 그리디하게 방향을 선택하되, E까지 도착이 가능한 범위내에서 방향 우선순위에 따라 이동을 하면 정답이 된다.

 

추가로 S지점에서 E지점으로 이동할때 불가능한 경우를 찾아야 하는데, 이 방법은 다음과 같다.

 

S지점에서 E지점까지 dist = |x1-x2| +|y1-y2|를 이용하여 dist가 k보다 크다면 이동이 불가능하다. 또한, k-dist의 값이 짝수가 아니면 이동이 불가능하다. 

 

왜냐하면 dist라는 값은 S에서 E지점까지의 최단거리를 의미하고 k-dist는 E지점에서 어딘가로 나갔다가 돌아올 수 있는 이동횟수이어야 하는데 이 값이 짝수 일때는 [(왔다, 갔다) or (탈출, 진입)] 이렇게 한 쌍으로 묶을 수 있는데 홀수면 나갔다가 돌아올 횟수가 부족하기 때문에 E로 이동자체가 불가능하다.

 

[소스 코드]

 

#include <string>
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

int dx[4] = {0,-1,1,0};
int dy[4] = {1,0,0,-1};
string answer;
bool fin = false;

int left_dist(int a1, int a2, int b1, int b2)
{
    return abs(a1-b1) + abs(a2-b2);
}

void dfs(int left, int x, int y, int n, int m, int r, int c)
{
    if(left==0)
    {
        fin=true;
        return;
    }
    for(int i=0; i<4; i++)
    {
        int nx = x + dy[i];
        int ny = y + dx[i];
        
        if(nx <= 0 || ny <= 0 || nx >= n+1 || ny >= m+1) continue;
        
        int diff = left_dist(nx,ny,r,c);
        if(left>=diff) 
        {
            if(i==0) answer.push_back('d');
            else if(i==1) answer.push_back('l');
            else if(i==2) answer.push_back('r');
            else if(i==3) answer.push_back('u');
            dfs(left-1,nx,ny,n,m,r,c);
            if(fin) return;
        }
    }
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    
    int dist = abs(x-r) + abs(y-c);
    if(k-dist < 0 || (k-dist)%2!=0) {answer = "impossible"; return answer;}
    dfs(k,x,y,n,m,r,c); 
    return answer;
}

 

굳