이번 문제는 프로그래머스의 레벨 3 미로 탈출 명령어 문제이다.
문제를 차근차근 읽어보도록 하자.

매개변수로 n, m, x, y, r, c, k 7개의 값이 주어진다.
순서대로, 판의 크기, 시작점, 도착점, 경로 길이를 의미한다.
주어진 경로 길이만큼 움직여 미로를 탈출할 수 있는 지 보는 문제이다.

n, m은 최대 50까지 주어질 수 있다.
x, y, r, c는 1 ~ n, m까지 주어질 수 있다.
경로의 길이는 최대 2500까지 주어지며, 0인 경우는 없다.
가능한 모든 경로 중, 사전 순으로 가장 빠른 경로를 반환해라!

문제를 어떻게 해결할 수 있을까?

BFS

처음에는 BFS로 해결하려 시도했다.
pair<pair<int, int>, pair<int, string>>을 선언하여 사용했는데,
시간초과가 날 것 같다고 생각하면서도 일단 구현해 보았다.

아래와 같이 BFS 핵심 함수를 구현했다.

string add_road(int dir, string road) {
	if (dir == 0)
		return road + "u";
	if (dir == 1)
		return road + "r";
	if (dir == 2)
		return road + 'd';
	if (dir == 3)
		return road + 'l';
}

void bfs(int n, int m, int x, int y, int r, int c, int k) {
	queue<piiis> bfs_q;
	bfs_q.push({ { x, y }, {0, ""} });

	while (!bfs_q.empty()) {
		int curr_x = bfs_q.front().first.first;
		int curr_y = bfs_q.front().first.second;
		int curr_dist = bfs_q.front().second.first;
		string curr_road = bfs_q.front().second.second;
		bfs_q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = curr_x + dx[i];
			int ny = curr_y + dy[i];
			int n_dist = curr_dist + 1;
			string n_road = add_road(i, curr_road);
   
			if (nx <= 0 || nx > n || ny <= 0 || ny > m)
				continue;
			if (n_dist == k && (nx != r || ny != c))
				continue;
			if (n_dist == k && nx == r && ny == c) {
				res_vec.push_back(n_road);
				continue;
			}

			bfs_q.push({ { nx, ny }, { n_dist, n_road } });
		}
	}

	if (res_vec.size() == 0)
		res_vec.push_back("impossible");
}

하지만 안타깝게도 대부분의 케이스에서 시간초과가 발생했다.
예상은 하고 있었지만, 뭐가 문제였을까?

지금 내 로직은 모든 경로를 다 훑어야 끝이 난다.
그럼, 경로가 최대로 2500인 경우에는, 당연히 시간초과가 발생할 것이다.
2500 길이까지 가능한 경로가 아니더라도 모두 탐색하게 되는 것이다.
하나의 경로를 탐색할 때마다 ^4만큼 늘어나는 격이니, 시간초과가 난다.

나는 지금부터 문자열 순으로 가장 빠른 경로라는 점을 이용하려 한다.
표현 가능한 문자는 d, l, r, u가 있다.
그럼 방문 순서 또한 문자에 맞춰 d, l, r, u로 둔다면?
그 중 가장 처음 찾아지는 경로는 문자열 순으로 가장 빠르지 않을까?

if (n_dist == k && nx == r && ny == c) {
				res_vec.push_back(n_road);
				finded = true;
				break;
			}

			bfs_q.push({ { nx, ny }, { n_dist, n_road } });
		}

		if (finded)
			break;

위와 같이 finded flag를 추가해 즉시 종료를 하도록 해보았다.
하지만, 결과는 동일했고 오히려 틀리는 케이스가 발생했다.

DFS

DFS로 노선을 틀기로 결심했다.
사실 impossible한 경우를 모두 들를 때를 생각해, 배제했었다.
하지만 일단 구현을 해보기로 결심했다.

DFS를 통해 위에 언급했던, 문자 순서대로 방문하도록 하자.
단, 시간을 줄이기 위해 impossible의 경우를 가지치기 했다.

if (abs(curr_x - r) + abs(curr_y - c) > (k - depth))
		return;
	// 현재 위치 -> 목적지 거리가 남은 거리보다 길면 바로 제거
	// impossible이 되는 경우를 제거한다.

위의 조건을 통해 가지치기를 하면, 미리 impossible을 방지할 수 있다.
거리가 2500일 경우, 2500까지 들어가지 않아도 되는 것이다.
또한, 경로를 찾자마자 종료시키기 위해 flag를 만들어 주었다.

void dfs(int n, int m, int curr_x, int curr_y, int r, int c, int k, int depth, string curr_road) {
	if (finded)
		return;

	if (depth == k && curr_x == r && curr_y == c) {
		res_vec.push_back(curr_road);
		finded = true;
		return;
	}

	if (abs(curr_x - r) + abs(curr_y - c) > (k - depth))
		return;
	// 현재 위치 -> 목적지 거리가 남은 거리보다 길면 바로 제거
	// impossible이 되는 경우를 제거한다.

	for (int i = 0; i < 4; i++) {
		int nx = curr_x + dx[i];
		int ny = curr_y + dy[i];

		if (nx <= 0 || nx > n || ny <= 0 || ny > m)
			continue;

		dfs(n, m, nx, ny, r, c, k, depth + 1, add_road(i, curr_road));
	}
}

위와 같은 코드로 제출을 해보았다.
하지만 안타깝게도 마지막 케이스에서만 시간초과가 발생했다.
image

결국 마지막 케이스는 다른 사람의 풀이를 참고하게 되었다.

마지막 가지치기 조건

다른 사람의 풀이를 보니 하나의 조건이 더 있었다.
애초에 impossible로 귀결되는 경우를 계산해 DFS를 실행하지 않았다.

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

코드의 시작을 위와 같이 시작하는 것이다.
remain > k는 시작점 -> 목적지의 거리가 남은 거리보다 긴 경우이다.
(k - remain) % 2 != 0의 경우는 전혀 생각지도 못한 조건이다.

만약 가야할 거리에서 시작점 -> 목적지를 뺀 값이 홀수라면?
다른 곳을 방문했다가, 그대로 그 거리만큼 돌아와야 하기 때문에 돌아올 수 없다.
다시 말해, 추가 거리 * 2만큼 움직였다가 목적지로 와야한다는 말이다.
즉, 짝수가 아니면 애초에 DFS를 실행할 필요가 없다!

특수한 조건을 떠올리는 것이 관건이었던 문제이다.
실제 시험 시간이었다면, 풀 수 없었을 것 같다.