[Programmers] 미로 탈출 명령어

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

사전순으로 가장 빠른 경로를 구해야 하므로 그리디 하게 [d, l, r, u] 순으로 백트래킹하면 되는 문제였습니다.

시간을 단축시키기 위해 현재 지점과 탈출 지점 사이의 맨해튼 거리를 구해 거리가 안될 경우 가지치기를 진행했습니다.

 

	#include <string>
	#include <vector>
	#include <set>
	#include <iostream>
	#include <cmath>
	using namespace std;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
	char c[4] = {'d', 'l', 'r', 'u'};
	int N, M, K;
	bool flag;
	pair<int, int> target;
	set<string> s;
	void func(int y, int x, string text, int cnt)
	{
	if (flag)
	{
	return;
	}
	if (abs(y - target.first) + abs(x - target.second) > K - cnt)
	{
	return;
	}
	if (cnt == K)
	{
	if (y == target.first && x == target.second)
	{
	s.insert(text);
	flag = true;
	}
	return;
	}
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 1 || nextY > N || nextX < 1 || nextX > M)
	{
	continue;
	}
	text += c[k];
	func(nextY, nextX, text, cnt + 1);
	text.pop_back();
	}
	}
	string solution(int n, int m, int x, int y, int r, int c, int k) {
	N = n, M = m, K = k;
	target = {r, c};
	int len = abs(x - r) + abs(y - c);
	if (len > k || (k - len) % 2)
	{
	return "impossible";
	}
	func(x, y, "", 0);
	return (s.empty() ? "impossible" : *s.begin());
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~