[프로그래머스] Level 3. 미로 탈출 명령어

 

https://school.programmers.co.kr/learn/courses/30/lessons/150365?language=cpp

프로그래머스

 

해결 방법

이동거리 K가 고정되어있다. 시작지점에서 끝 지점에 가기 위해서 가야하는 횟수는 정해져있다. (오른쪽2번, 아래2번) 이런식이다. 예제 1번에서, 오른쪽1번, 왼쪽2번만 가면 도달할 수 있는데 총 5번을 이동하라고 했다. 즉, 남은 2번은 위-아래를 하던지 왼-오 를 하던지, 의미없는 이동을 하라는 의미이다. 

• 왼,오,위,아래를 각각 필수적으로 몇번 이동해야하는지를 찾는다. (x,y)와 (a,b)를 다이렉트로 간다고 생각하면된다.
• k에서 필수이동개수를 뺀 다음 2로 나누면, 의미없는 왔다갔다의 횟수가 된다. 이 값을 dummy에 넣어준다.
• 알파벳이 작은 순서는 dlru 이다. 이 순서대로 움직이려고 시도해본다. 움직이는 시도는 다음과 같은 순서로 진행된다. 아래쪽 이동을 예시로 설명하면 다음과 같다. 
  1. 만약 아래쪽으로 더 이동할수 없다면 false를 리턴한다.
  2. 만약 cd가 0보다 크다면 (아래쪽으로 이동할 횟수가 남아있다면)  횟수를 차감한 후 아래로 한칸 이동시킨다. answer에 'd'를 추가한다.
  3. 만약 cd는 없지만 dummy값이 있다면, 위-아래 의미없는 이동을 하라는 뜻이다. dummy를 하나 줄이고, cd, cu 를 한개씩 올린 후 아래이동한다. (아래이동은 바로 하므로 실질적으로 cd는 올리지않아도 된다) 
  4. 만약 cd도 없고 dummy도 없다면, 아래쪽으로는 더이상 이동할 수 없다는 의미이다. false를 리턴한다.
• 이동가능한 변수들이 모두 0이라면, 탐색이 끝난것이다. 결과로 나온 answer의 길이가 k와 동일하다면 answer을, 아니면 impossible을 리턴한다. 

 

• 이 검사를 시작하기 전에, 만약 필수적으로 이동해야 하는 수(다이렉트로 갔을때) 보다 K가 작다면, 검사를 진행할 필요 없이 "impossible" 이다.
• 또한, k- (필수이동수) 를 했는데 2로 나누어 떨어지지 않을 경우, (왼-오) 혹은 (위-아래) 세트가 맞춰지지 않는다는 의미이므로, 도착지에 도달할 수 없다는 의미이다. "impossible" 이다.

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

using namespace std;

bool tryDown(int n, string& answer, int& x, int& d, int& u, int& dummy){
    if(x+1 <0 || x+1 >= n ) return false;
    else if(d>0){  d--; answer +="d"; x ++; return true; }
    else if(dummy > 0){ dummy--; u++; x++; answer +="d"; return true; }
    return false;
}

bool tryUp(int n, string& answer, int& x, int& d, int& u, int& dummy ){
    if(x-1<0 || x-1 >=n) return false;
    else if(u >0){ u--; answer +="u"; x--; return true;}
    else if(dummy >0){dummy--; d++; x--; answer+="u"; return true;}
    return false;
}

bool tryLeft(int m, string& answer, int& y, int& l, int& r, int& dummy){
    if(y-1<0 || y-1 >=m) return false;
    if(l > 0){ l--; answer +='l'; y--; return true; }
    if(dummy >0){ dummy--; r++; y--; answer += 'l'; return true; }
    return false;
}

bool tryRight(int m, string& answer, int&y, int& l , int& r , int& dummy){
    if(y+1 <0 || y+1>=m) return false;
    if(r >0){ r--; answer +="r"; y++; return true;}
    else if(dummy >0){dummy--; l++; y++; answer +='r'; return true;};
    return false;
}


string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    x-=1; y-=1; r-=1;c -=1; //인덱스 번호로 변환
    int cd = 0 ; int cl = 0; int cr = 0; int cu = 0; int dummy=0; //왓다갓다하는 세트
    
    if(x>r) cu= x-r; else cd = r-x;
    if(y>c) cl= y-c; else cr = c-y;
    
    if(k < cd+cl+cr+cu ||(k-cd-cl-cr-cu)%2 !=0 ) return "impossible";
    dummy = (k-(cd+cl+cr+cu))/2;
    
    
    while(cd !=0 || cl !=0 || cr != 0 || cu !=0 || dummy != 0){
        if(tryDown(n, answer, x,cd,cu,dummy))continue;
        if(tryLeft(m,answer,y,cl,cr,dummy))continue;;
        if(tryRight(m,answer,y,cl,cr,dummy))continue;
        tryUp(n,answer,x,cd,cu,dummy);
    }
    
    if(answer.size() != k) return "impossible";
    return answer;
}

 

마무리하며

뭔가 아이디어는 그럴듯 한데, 자료구조를 잘 활용하지 못하는 느낌이 든다. 아무래도 자료구조를 여러가지 활용해보도록 노력해야 할 것 같다.