백준 Gold 4 DSLR

DSLR (백준 Gold 4)

https://www.acmicpc.net/problem/9019

다음의 4가지 연산법이 존재한다 가정

• D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
  
• S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
  
• L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
  
• R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
  

이 4가지 연산을 사용하여
특정 값을 다른 값으로 바꾼다고 하였을 때

그 최소 연산법을 출력하는 문제

• n개의 시작값과 목표값이 주어진다
  
• 최소 연산법이 여러 개 존재한다면 그 중 아무거나 출력
  

풀이 방법

• 각각의 DSLR 연산을 구현하고
  start -> target 을 bfs로 풀 수 있는 문제
  

• 다만, 시간초과가 계속 발생하여서
  역추적을 통해 문제를 풀 수 있었다
  

1. DSLR 연산을 구현
   
2. BFS를 통해 최소 연산법을 구하기
   
3. 최소 연산법을 구할때, string을 저장하지 말고 이전 벡터가 저장한 위치와 연산법을 저장
   
4. 마지막에 이전 저장해둔 위치들을 타고가면서 string을 만든 후, 뒤집어주기
   

제출 코드

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>

using namespace std;

const char ords[4] = { 'D','S', 'L', 'R' };

int Dfunc(int n)
{
	return (n * 2) % 10000;
}

int Sfunc(int n)
{
	n--;

	if (n < 0)
		return 9999;

	return n;
}

int Lfunc(int n)
{
	if (n < 1000)
		return n * 10;

	int v = n / 1000;

	int ret = (n - (v * 1000)) * 10 + v;

	return ret;
}

int Rfunc(int n)
{
	int v = n % 10;

	int ret = n / 10 + v * 1000;

	return ret;
}

struct infos
{
	int prev;
	int now;
};

void FindRoute(int start, int target)
{
	queue<infos> pq;

	pq.push({ -1,start });

	vector<bool> visit(10000, false);
	vector<pair<int,int>> prev(10000);

	visit[start] = true;
	prev[start] = { -1,-1 };

	while (true)
	{
		int prevV = pq.front().prev;
		int nowV = pq.front().now;
		pq.pop();

		if (nowV == target)
		{
			string ret = "";

			int idx = nowV;
			while (prev[idx].first != -1)
			{
				ret.push_back(ords[prev[idx].second]);
				idx = prev[idx].first;
			}

			reverse(ret.begin(), ret.end());

			cout << ret << '\n';

			return;
		}

		int nV = Dfunc(nowV);
		if (visit[nV] == false)
		{
			pq.push({ nowV,nV });
			visit[nV] = true;
			prev[nV] = { nowV,0 };
		}

		nV = Sfunc(nowV);
		if (visit[nV] == false)
		{
			pq.push({ nowV,nV });
			visit[nV] = true;
			prev[nV] = { nowV,1 };
		}

		nV = Lfunc(nowV);
		if (visit[nV] == false)
		{
			pq.push({ nowV,nV });
			visit[nV] = true;
			prev[nV] = { nowV,2 };
		}

		nV = Rfunc(nowV);
		if (visit[nV] == false)
		{
			pq.push({ nowV,nV });
			visit[nV] = true;
			prev[nV] = { nowV,3 };
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	vector<pair<int, int>> orders(n);

	for (int i = 0; i < n; i++)
	{
		cin >> orders[i].first >> orders[i].second;
	}

	for (auto& p : orders)
	{
		FindRoute(p.first, p.second);
	}

	return 0;
}

결과

처음에는 단순한 BFS + 구현 계열의 문제라 생각하였으나
계속 시간초과가 발생하여 ‘역추적’을 통해

‘이전 값’을 보관한 후,
마지막에 string으로 합치는 방식을 통해 문제를 해결하였다