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

#include <string>
#include <vector>

using namespace std;

string answer = "";

void dfs(int n, int m, int x, int y, int r, int c, int k, int currCount, string currPath)
{
    int manhattanRange = abs(x - r) + abs(y - c);                    
    if (manhattanRange + currCount > k)
    {        
        return;
    }
    if (x == r && y == c && k == currCount)
    {
        answer = currPath;
        return;
    }
    if(answer != "")
    {
        return;
    }

    if (x + 1 <= n)
    {
        dfs(n, m, x + 1, y, r, c, k, currCount + 1, currPath + 'd');
    }
    if (y - 1 >= 1)
    {
        dfs(n, m, x, y - 1, r, c, k, currCount + 1, currPath + 'l');
    }
    if (y + 1 <= m)
    {
        dfs(n, m, x, y + 1, r, c, k, currCount + 1, currPath + 'r');
    }
    if (x - 1 >= 1)
    {
        dfs(n, m, x - 1, y, r, c, k, currCount + 1, currPath + 'u');
    }
    
}


string solution(int n, int m, int x, int y, int r, int c, int k) 
{    
    int manhattanRange = abs(x - r) + abs(y - c);                    
    if ((k - manhattanRange) % 2 != 0)
    {        
        answer = "impossible";
    }
    else
    {
        dfs(n, m, x, y, r, c, k, 0, "");
    }
    
    if (answer == "")
    {
        answer = "impossible";
    }

    return answer;
}

 

풀이

1. 사전순으로 DFS를 하여 (d,l,r,u 순으로 탐색) 정렬할 필요없이 첫 번째로 나온 답이 답일 수 있도록 탐욕적으로 해결

2. 각 이동 시마다 맨해튼거리(현재 위치에서 도착점까지의 거리)를 측정하여 현재 위치에서 얼마나 걸리는지 확인

3. 현재 위치와 도착점, 이동한 거리가 같을 경우 정답으로 처리하고 남은 DFS들은 return 처리

4. 처음 시작점에서, 맨해튼거리와 k의 차가 홀수일 경우 도달할 수 없으므로 미리 불가능 처리

 

 

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

프로그래머스