선밥의 공부하는 블로그

미로 탈출 명령어

문제 링크

미로 탈출 명령어

분석

(x, y)에서 시작해 (r, c)로 탈출하면서 다음 조건을 만족하는 문자열 경로를 반환해야합니다.

  • 격자의 바깥으로는 나갈 수 없습니다.
  • 총 이동 횟수는 정확하게 k번이어야 합니다.
  • 방문 했던 격자를 또 방문 할 수 있습니다.
  • 사용 가능한 이동 방향은 왼쪽, 오른쪽, 위쪽, 아래쪽(l, r, u, d)입니다.
  • 이 경로는 사전 순으로 가장 빠른 문자열이어야 합니다.

  • 위의 조건으로 미로를 탈출할 수 없는 경우 "impossible"를 반환해야합니다.

  • n과 m은 격자의 크기를 뜻합니다.
  • x와 y는 출발 위치를 뜻합니다.
  • r과 c는 탈출 지점을 뜻합니다.
  • k는 탈출까지 이동해야 하는 거리를 뜻합니다.

풀이

#include <string>
#include <cmath>

using namespace std;

// 정답 문자열
string answer = "";
// 행과 열의 개수 저장
int mapSize[2];
// 목표 행과 목표 열 저장
int targetLocation[2];
// 이동 제한 횟수
int countLimit;

// 방향 아래, 왼쪽, 오른쪽, 위를 의미
// 사전순으로 정렬하여 사용
int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};
char directionChar[] = {'d', 'l', 'r', 'u'};

void dfs(int x, int y, string path, int depth)
{
    // 이미 정답을 찾은 경우 더 이상 탐색하지 않는다.
    // 사전순으로 가장 빠른 경로만 필요하다.
    if (!answer.empty())
    {
        return;
    }
    
    // 현재 위치에서 목표까지의 거리
    int remainDistance = abs(x - targetLocation[0]) + abs(y - targetLocation[1]);
    // 남은 이동 가능 횟수
    int remainMove = countLimit - depth;
    
    // 가지치기
    // 1. 남은 거리보다 움직일 수 있는 횟수가 부족한 경우
    // 2. 남은 횟수 - 거리가 홀수인 경우
    if (remainDistance > remainMove || (remainMove - remainDistance) % 2 != 0)
    {
        return;
    }
    
    // 이동 횟수를 다 사용한 경우
    if (depth == countLimit)
    {
        // 목표 위치에 도착했다면 정답
        if (x == targetLocation[0] && y == targetLocation[1])
        {
            answer = path;
        }
        return;
    }
    
    // 4방향을 사전 순서대로 이동 시도
    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 격자 범위를 벗어나지 않는 경우
        if (nx > 0 && nx <= mapSize[0] && ny > 0 && ny <= mapSize[1])
        {
            dfs(nx, ny, path + directionChar[i], depth + 1);
        }
    }
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    // 맵 크기 저장
    mapSize[0] = n;
    mapSize[1] = m;
    
    // 목표 위치 저장
    targetLocation[0] = r;
    targetLocation[1] = c;
    
    // 최대 이동 횟수 저장
    countLimit = k;
    
    // 현재 위치에서 목표 위치까지의 최소 거리 계산
    int distance = abs(x - r) + abs(y - c);

    // 도달이 불가능한지 확인
    // 1. 이동 제한 횟수보다 최소 이동 거리가 작은 경우
    // 2. 이동 제한 횟수 - 거리가 홀수인 경우 횟수에 맞춰서 도착할 수 없다.
    if (distance > k || (k - distance) % 2 == 1)
    {
        return "impossible";
    }
    
    dfs(x, y, "", 0);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(4^k)$입니다.

  • DFS 재귀 호출 $O(4^k)$

공간 복잡도는 $O(K^2)$입니다.

  • DFS 재귀 호출 스택 $O(k)$
  • 경로 문자열 string path $O(k^2)$
    • DFS 호출마다 문자열의 복사가 발생하기 때문입니다.
  • $O(k) + O(k^2)$
테스트 성능

테스트 1 〉 통과 (0.05ms, 4.14MB)
테스트 2 〉 통과 (0.05ms, 4.11MB)
테스트 3 〉 통과 (0.01ms, 4.16MB)
테스트 4 〉 통과 (0.01ms, 3.66MB)
테스트 5 〉 통과 (0.01ms, 4.18MB)
테스트 6 〉 통과 (0.01ms, 4.12MB)
테스트 7 〉 통과 (0.01ms, 4.05MB)
테스트 8 〉 통과 (0.01ms, 4.01MB)
테스트 9 〉 통과 (3.84ms, 9.87MB)
테스트 10 〉 통과 (3.69ms, 9.95MB)
테스트 11 〉 통과 (4.47ms, 9.87MB)
테스트 12 〉 통과 (4.51ms, 9.73MB)
테스트 13 〉 통과 (4.15ms, 9.87MB)
테스트 14 〉 통과 (4.51ms, 9.81MB)
테스트 15 〉 통과 (4.36ms, 9.9MB)
테스트 16 〉 통과 (3.79ms, 9.73MB)
테스트 17 〉 통과 (4.36ms, 9.86MB)
테스트 18 〉 통과 (4.46ms, 9.87MB)
테스트 19 〉 통과 (3.91ms, 9.81MB)
테스트 20 〉 통과 (4.58ms, 9.77MB)
테스트 21 〉 통과 (3.97ms, 9.86MB)
테스트 22 〉 통과 (4.25ms, 9.89MB)
테스트 23 〉 통과 (4.42ms, 9.87MB)
테스트 24 〉 통과 (4.38ms, 9.89MB)
테스트 25 〉 통과 (4.43ms, 9.82MB)
테스트 26 〉 통과 (4.32ms, 9.82MB)
테스트 27 〉 통과 (4.38ms, 9.79MB)
테스트 28 〉 통과 (4.37ms, 9.86MB)
테스트 29 〉 통과 (4.35ms, 9.89MB)
테스트 30 〉 통과 (4.34ms, 9.75MB)
테스트 31 〉 통과 (0.01ms, 3.66MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기

최근 글