[Algorithm] Programmers :: 미로 탈출 명령어

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

프로그래머스

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int width, height, destY, destX, maxCount;
int dirs[4][2] = { {1,0}, {0,-1}, {0,1}, {-1,0} };
char dirAlphabets[4] = { 'd', 'l', 'r', 'u'};
string answer = "";
string result = "impossible";
bool isBreak = false;
 
 
int getDistance(int y1, int x1, int y2, int x2)
{
    return abs(y2 - y1) + abs(x2 - x1);
}
 
void DFS(int y, int x, int count)
{
    if (!isBreak)
    {
        int distance = getDistance(destY, destX, y, x);
 
        if (distance > count) return;
        if ((count - distance) % 2 != 0) return;
 
        if (count == 0)
        {
            if (y == destY && x == destX)
            {
                isBreak = true;
                result = answer;
 
            }
            return;
        }
 
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = y + dirs[i][0];
            int nextX = x + dirs[i][1];
 
            if (nextY < 1 || nextY > height) continue;
            if (nextX < 1 || nextX > width) continue;
 
            answer.push_back(dirAlphabets[i]);
            DFS(nextY, nextX, count - 1);
            answer.pop_back();
        }
    }
}
 
 
 
string solution(int n, int m, int x, int y, int r, int c, int k)
{
    height = n;
    width = m;
    destY = r;
    destX = c;
    maxCount = k;
 
    DFS(x, y, k);
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 3;
    int m = 4;
    int x = 2;
    int y = 3;
    int r = 3;
    int c = 1;
    int k = 5;
 
    /*int n = 2;
    int m = 2;
    int x = 1;
    int y = 1;
    int r = 2;
    int c = 2;
    int k = 2;*/
 
    //int n = 3;
    //int m = 3;
    //int x = 1;
    //int y = 2;
    //int r = 3;
    //int c = 3;
    //int k = 4;
 
    cout << solution(n, m, x, y, r, c, k);
}
 
 
 

 

이거는... DFS의 특징을 살려야하는 문제였다.

DFS는 한쪽으로 먼저 파고드니, 가장 답일 가능성이 높은 루트를 탐색할 수 있었다.

가장 답일 가능성이 높은것이란 사전순이여야 한다는 것이다.

BFS로 할 경우, 왼쪽으로 뿌렸던게 다시 오른쪽으로 뿌려버릴 수 있다. 즉, count제한이 있기 때문에 언젠가 구하긴 하겠지만 너무 골고루 뿌리다보니 답을 구하는데 굉장히 오래 걸린다.

최단거리는 DFS보다 평균적으로 빨리구할 수 있겠지만, 이 문제는 최단거리를 구하는게 아니기 때문이다.

 

DFS는 그냥 우직하게 ddddddddddd 하다가 llllllllllllllllll 하는식으로 굉장히 사전순으로 하기때문에 count가 0일때 목표지점일경우 그때의 명령어가 정답이라는 것이 보장된다.

 

다만, 당연히 결국 4방향으로 뿌려지는것이기 때문에 가지치기가 필요하다.

일단 현재위치에서 목표지점까지의 최단거리가 count보다 크면 가지치기 해준다. 아예 목적지로 이동자체가 불가능하기 때문이다.

 

그리고 이게 중요한데, count보다 목표지점까지의 최단거리가 크더라도, (현재 count - 목표지점까지의 최단거리)가 홀수일 경우도 가지치기 해줘야한다.

목표지점에 도착했을 때 아직 count가 짝수개 남았다면, 그냥 목표지점에서 위로갔다 아래로가든, 왼쪽으로갔다 오른쪽으로 가든 해서 최종적으로 목표지점에서 count가 0이되게 할 수 있기 때문이다.

뭐 사전순이니 굳이 따지자면 내려갔다 위로올라간게 정답이 되시겠다.

 

쨌든 짝수개가 남았다면 목표지점에서 전부 소모해버릴 수 있는데, 홀수개라면 목표지점에서 0개가 될 수 없기 때문에 가지쳐줘야 한다.