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

미로탈출명령어 (프로그래머스 Level 3)

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

문제 자체는 조금 독특한 최단거리 찾기였던 것 같다
주어진 ‘k’만큼의 거리만큼만 이동하여 목적지에 도달하되
명령어의 조합이 ‘사전순’으로 가장 작은 녀석을 고르는 문제였다

따라서 사전순으로 가까운 순으로 DFS를 돌리면 된다고 생각하였으나
일부 문제에서 시간초과가 발생하였다
아마 ‘impossible’을 판단하는데 시간이 너무 오래걸린다고 판단하여
‘현재 목적지까지 남은 거리’(remain)가
남은 k보다 크거나
남은 거리는 ‘홀수’인데, k는 ‘짝수’인 경우는
더 이상 DFS를 탐색하여도 답을 찾을 수 없으므로 걸러주는 방식을 사용하였다

Code

#include <string>
#include <vector>
#include <queue>

using namespace std;

const string dirCom[4] = { "d","l" ,"r" ,"u" };

void solution(int n, int m, int x, int y, int r, int c, int k, string& answer, string nowCom)
{
	// 정답에 도달
	if (k == 0 && x == r && y == c)
	{
		answer = nowCom;
		return;
	}
	else 
	{
		// 이미 k 개수가 
		if (k <= 0)
		{
			answer = "impossible";
			return;
		}
		
		// abs(x - r) + abs( y - c) 의 값이 k보다 큰 상황
        // 이쪽 루트로는 뭘 해도 도달 불가하다
        int remain = abs(x - r) + abs(y - c);
        if (remain > k ||
            (remain % 2 == 1 && k % 2 == 0))
        {
            answer = "impossible";
            return;
        }
	}

	// 범위 벗어남
	if (x < 0 || x >= n ||
		y < 0 || y >= m)
	{
		return;
	}

	// 아래
	if (answer == "" || answer == "impossible")
	{
		solution(n, m, x + 1, y, r, c, k - 1, answer, nowCom + dirCom[0]);
	}

	// 좌
	if (answer == "" || answer == "impossible")
	{
		solution(n, m, x, y - 1, r, c, k - 1, answer, nowCom + dirCom[1]);
	}

	// 우
	if (answer == "" || answer == "impossible")
	{
		solution(n, m, x, y + 1, r, c, k - 1, answer, nowCom + dirCom[2]);
	}

	// 위
	if (answer == "" || answer == "impossible")
	{
		solution(n, m, x - 1, y, r, c, k - 1, answer, nowCom + dirCom[3]);
	}

}

string solution(int n, int m, int x, int y, int r, int c, int k) {
	string answer = "";

	// 어차피 모든 경로를 다 뒤져야 한다면
	// dfs가 오히려 빨리 찾을 수 있지 않을까?
	// 이건 조건에 맞는 가장 '적은 수'를 찾는 것이기에
	solution(n, m, x - 1, y - 1, r - 1, c - 1, k, answer, "");

	return answer;
}