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

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

프로그래머스

 

미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.

이 말은 즉, 그리디로 풀라는 얘기와 같다.

 

각 이동 방향 문자를 사전 순으로 나열하면, 아래[d] -> 왼[l] -> 오[r] -> 위[u] 순서가 된다.

즉, 목표 위치로 가는 경로를 구할 때, 다음과 같은 규칙이 생긴다.

• 가장 아래로 많이 간다.
• 아래로 갈 수 없다면, 왼쪽으로 간다.
• 왼쪽으로 갈 수 없다면, 오른쪽으로 간다.
• 오른쪽으로 갈 수 없다면, 위쪽으로 간다.

위 규칙을 지키되, 이동 횟수를 모두 소모한 후의 위치가 목표 위치여야 한다.

 

 

이동 방향 순서가 정해져있고, 여러 경우의 수가 나올 수 있기 때문에, DFS를 통해 접근했다.

아래 -> 왼 -> 오 -> 위 순서로 탐색하며, 조건에 맞지 않으면 틀린 위치까지 되돌아가도록 풀었다.

 

먼저, 위 방식은 목표를 두고 이동하는 것이 아니기 때문에, 모든 이동을 고려하여 탐색할 것이다.

심지어, 이 문제에서는 중복된 위치를 밟아도 되기 때문에, 방문 체크 또한 하지 못한다.

 

따라서, 시간초과를 해결하기 위한 두 조건을 달아줘야 한다.

첫 번째 조건

• DFS와 그리디를 통해, 사전 순으로 가장 빠른 경로로 탐색할 것이다.
• 근데, 현재 위치에서 목표까지 남은 거리가, 남은 이동 횟수보다 많다면?
  • 당장 DFS와 그리디를 무시하고 최단으로 이동해도 목표 위치에 갈 수 없다는 의미이다.
  • 따라서, 이런 상황이라면, 곧바로 false로 반환하면 된다.
• 이 조건만 달아줘도 거의 풀린다. 31번 테스트케이스만 빼고

 

두 번째 조건

• 문제를 보면, 중복된 위치를 밟아도 된다.
• 만약, 사전 순으로 가장 빠른 경로로 목표 위치에 도달하고, 이동 횟수가 남아있다면, 그냥 옆으로 왔다 갔다만 해도 된다.
• 근데, 같은 위치에서 왔다갔다를 했을 때 원래 위치로 되돌아오려면, 왔다 갔다를 한 횟수가 짝수여야 한다.
• 즉, 목표까지 남은 거리가 홀수인데, 남은 이동 횟수가 짝수라면, 해당 위치에서는 어떻게 이동해도 목표 위치에 딱 맞게 도달할 수 없다.

#include <string>
#include <vector>
using namespace std;

// 아래(d), 왼(l), 오(r), 위(u) 순서
string Dir[]{ "d", "l", "r", "u" };
int dy[]{ 1, 0, 0, -1 };
int dx[]{ 0, -1, 1, 0 };

// 미로 찾기 함수 { 문자열, 결과 } 반환
pair<string, bool> DFS(int n, int m, int x, int y, int r, int c, int k, string Str)
{
	// 현재 위치가 목표 위치이고, 남은 이동 횟수가 0이라면 통과
	if (y == r && x == c && k == 0)
	{
		if (y == r && x == c) return { Str, true };
		else return { Str, false };
	}

	// 목표까지 남은 거리
	int Dist = abs(y - r) + abs(x - c);

	// 목표까지 남은 거리가 남은 이동 횟수보다 많으면, 갈 수 없으므로 false 반환
	if (Dist > k) return { Str, false };

	// 목표까지 남은 거리가 홀수인데, 남은 이동 횟수가 짝수라면
	// 해당 위치에서는 어떻게 이동해도 목표 위치에 딱 맞게 도달할 수 없다.
	if (Dist % 2 != 0 && k % 2 == 0) return { Str, false };

	// 아래(d), 왼(l), 오(r), 위(u) 순서로 탐색
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i], nx = x + dx[i];
		if (ny < 1 || nx < 1 || ny > n || nx > m) continue;

		pair<string, bool> Ret = DFS(n, m, nx, ny, r, c, k - 1, Str + Dir[i]);
		if (Ret.second) return { Ret.first, true };
	}

	return pair<string, bool> {string(), false};
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
	::swap(x, y); // 편의상 { y, x }로 사용하기 위해서, x와 y를 스왑

	// 미로 찾기 수행 { 문자열, 결과 }
	pair<string, bool> Answer = DFS(n, m, x, y, r, c, k, string());

	// 미로 찾기 결과가 성공이라면, 문자열 리턴
	if (Answer.second) return Answer.first;
	else return "impossible";
}