[프로그래머스] 미로 탈출 명령어 c++

처음엔 BFS로 접근했다가 시간초과를 당했다...!

 

이 문제를 풀 때 중요한 것은 사전순으로 빠른 경로를 출력한다는 것이다.

따라서 d > l > r > u 순으로 움직일 수 있는 만큼 먼저 움직여야 한다.

 

우선 미로에는 별다른 장애물이 없기 때문에

시작점과 끝점의 거리는 abs( x - r ) + abs( y - c)로 구할 수 있다.

이 거리가 두점사이의 최단경로의 거리이므로,

만약 이 값이 k보다 크다면 k만큼 이동해도 끝점에 도달하지 못하므로 impossible이다.

 

또한 k에서 최단 경로의 거리를 뺐을 때 이 값이 홀수라면, 

끝점에 도달하지 못하므로 impossible이다.

(예를 들어, 최단경로만큼 이동해서 끝점에 도달하고 왔다갔다 하면서 횟수만 채운다고 생각했을 때, 왔다갔다하는 횟수는 짝수여야지 다시 끝점으로 들어올 수 있다!)

 

사전으로 가장 빠른 것은 d이다.

따라서 현재 위치에서 끝점까지의 거리가 횟수내로 들어 갈 수 있고,

미로의 범위 내에서 d를 수행한다············(1)

 

같은 방법으로 l을 수행한다.············(2)

 

d와 l을 수행했을때, 현재 위치에서 끝점까지의 거리의 횟수 여유가 있다면

rl을 반복 수행한다.············(3)

(rl을 수행하는 이유는 ud를 수행하는 것보다 사전순으로 빠르기 때문이다.

lr이나 du는 이미 (1),(2)의 과정으로 d와 l을 다 이동했기 때문에 불가능하다.)

 

이후, 끝점까지 d > l > r > u순으로 이동할 수 있을 만큼 이동한다.············(4)

 

 

 

실행 예제를 보면 다음과 같다.

 

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

using namespace std;

string solution(int n, int m, int x, int y, int r, int c, int k) {
  string answer = "";
  int curX = x, curY = y;
  int leftDistance = abs(x-r) + abs(y-c);
  if(leftDistance > k || (k-leftDistance)%2 == 1){
    return "impossible";
  }

  int moves[2][2] = {{1,0}, {0,-1}}; // d l
  char moveChar[2] = {'d', 'l'};

  for(int i=0; i<2; i++){
    while(leftDistance < k){
      int nx = curX + moves[i][0];      
      int ny = curY + moves[i][1];
      if(nx > 0 && nx <= n && ny > 0 && ny<= m){
        curX = nx;
        curY = ny;
        leftDistance = abs(curX-r) + abs(curY-c);
        answer += moveChar[i];
        k--;
      }
      else{
        break;
      }    
    }
  }
  while(leftDistance < k){
    k-=2;
    answer += "rl";
  }
  while(curX < r){
    answer += 'd';
    curX++;
  }
  while(curY > c){
    answer += 'l';
    curY--;
  }
  while(curY < c){
    answer += 'r';
    curY++;
  }
  while(curX > r){
    answer += 'u';
    curX--;
  }
  return answer;
}

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