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

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

프로그래머스

프로그래머스 - 미로 탈출 명령어 (2023 KAKAO BLIND RECRUITMENT)

문제 유형 : bfs/dfs

문제 난이도 : Level 3

 

문제 설명

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

 

 

풀이

일반적인 dfs로는 풀 수 없습니다. 처음부터 가장 사전순으로 먼저오는 탈출경로를 만들어내기는 힘들고,

모든 경우의 수를 구해보자니 시간이 오래 걸립니다.

 

대신, 변형된 dfs를 이용할 수 있습니다.

보통 격자에서 순회를 할 때, 상하좌우로 많이 움직이는데, 여기서는 사전순, 즉 d > l > r > u 순으로 가야 합니다.

그리고, 방문 여부에 vis[x][y]형태로 보통 저장하지만, 여기서는 정해진 시간에 맞춰서 목적지에 도착해야 합니다.

목적지에 도착하기 전에, 어느 지점으로 돌아가든 상관은 없습니다.

그러므로, vis[x][y][(남은 이동 수)]의 형태로 저장하고,

탐색 중 처음으로 남은 이동수가 0이고, 목적지에 도착했을 때 그 탈출경로가 사전순으로 앞에 오는 탈출경로가 될 수 밖에 없습니다.

사전순 우선순위로 이동을 해나가기 때문입니다.

 

추가로, 불가능한 경우를 빠르게 알아내는 방법이 있습니다.

만약 두 점 사이의 거리(가로축거리 + 세로축거리)가 k보다 크면, 불가능한 경우입니다. 어떤 노력을 해도 닿을 수 없습니다.

또한, k와 두 점 사이의 거리(가로축거리 + 세로축거리)의 홀짝여부가 다르면, 불가능한 경우입니다. k이내로 도달한다고 해도, 잔여 이동이 남아있고, 남은 잔여 이동은 홀수라서 어떤 방법을 쓰든 다시 그 위치로 돌아올 수 없습니다.

 

 

이 문제의 다른 풀이로는 우선순위 순으로 문자열에 글자를 추가해주는 방법이 있습니다. 탐색을 쓰지 않고요!

단순히 d, l r, u순으로 목적지에 도달할 때까지 붙이고, 남는 이동수는 du, lr, rl, ud의 우선순위로 채우는 방법이 있습니다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

// 하,좌,우,상 순으로 이동
vector<int> dx = {1, 0, 0, -1};
vector<int> dy = {0, -1, 1, 0};
vector<char> dir = {'d', 'l', 'r', 'u'};

// 시작 위치, 끝 위치, 방문 여부 담기
pair<int, int> from;
pair<int, int> to;
vector<vector<vector<bool>>> visited;

// 크기를 전역변수로 설정
int rowSize;
int colSize;

// 두 점 사이의 거리
int getDiff(pair<int, int> a, pair<int, int> b) {
    return abs(b.first - a.first) + abs(b.second - a.second);
}

// dfs
string dfs(pair<int, int> curr, int left, string prefix) {
	// 만약 가망이 없으면, 접어라(백트래킹)
    if (getDiff(curr, to) > left)
        return "";

    int x = curr.first;
    int y = curr.second;
	
    // 현재 위치와 남은 이동수로 체크
    visited[x][y][left] = true;

    //cout << x << " " << y << " " << left << " " << prefix << endl;

	// 만약 이동이 끝났으면
    if (left == 0) {
    // 만약 이동이 끝나고 목적지에 온게 맞다면
        if(x == to.first && y == to.second)
            return prefix;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        string str = prefix + dir[i];

        if (nx < 0 || ny < 0 || nx >= rowSize || ny >= colSize)
            continue;
        if (visited[nx][ny][left])
            continue;
        string s = dfs({nx, ny}, left - 1, str);
        // 만약 찾았다? 리턴
        if (s.size() != 0)
            return s;
    }

    return "impossible";
}

string solution(int n, int m, int x, int y, int r, int c, int k)
{
	// 처음부터 가능성이 없으면 종료
    int diff = getDiff({x, y}, {r, c});
    if (diff > k || diff % 2 != k % 2)
        return "impossible";

    rowSize = n;
    colSize = m;

	// 0-indexed로 수정
    from = {x - 1, y - 1};
    to = {r - 1, c - 1};

	// 방문 여부 초기화
    visited.resize(n, vector<vector<bool>>(m, vector<bool>(k + 1, false)));
	
    // dfs
    return dfs(from, k, "");
}