[BOJ]9019번: DSLR (c++)

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

9019번: DSLR

 

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MOD = 10000;
enum { D, S, L, R };
string dslr = "DSLR";
bool visit[MOD];
int bf[MOD];
char ops[MOD];

// D S L R 연산 결과 반환
int operation(int n, int op)
{
	int t_mod = MOD / 10;

	if (op == D)
	{
		return (n * 2) % MOD;
	}
	else if (op == S)
	{
		return (n + MOD - 1) % MOD;
	}
	else if (op == L)
	{
		return (n % t_mod) * 10 + n / t_mod;
	}
	else if (op == R)
	{
		return (n % 10) * t_mod + (n / 10);
	}
	return n;
}

// end숫자부터 start숫자까지 역추적해서 op출력
void print(int n)
{
	if (bf[n] == -1)
	{
		return;
	}

	print(bf[n]);

	cout << ops[n];
}

void bfs(int A, int B)
{
	// 큐에 start숫자 push
	queue<int> q;
	q.push(A);

	// 방문체크, 이전 인덱스 배열에 -1 저장.
	visit[A] = true;
	bf[A] = -1;

	while (!q.empty())
	{
		int n = q.front();
		q.pop();

		// end숫자에 도착하면 출력 후 종료
		if (n == B)
		{
			print(n);
			cout << '\n';
			return;
		}

		// DSLR 연산 4가지 진행
		for (int i = 0; i < 4; ++i)
		{
			// 다음 숫자를 아직 방문한적이 없다면
			int next = operation(n, i);
			if (!visit[next])
			{
				// 방문체크, 연산 char 저장, bf배열에 현재 숫자 저장.
				visit[next] = true;
				ops[next] = dslr[i];
				bf[next] = n;

				// 큐에 다음 숫자 push
				q.push(next);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin >> T;
	while (T--)
	{
		// 입력
		int A, B;
		cin >> A >> B;

		// 배열 초기화
		memset(visit, 0, sizeof(visit));
		memset(ops, 0, sizeof(ops));
		memset(bf, 0, sizeof(bf));

		// A ~ B로 변환하기 위한 최소 명령어 출력
		bfs(A, B);
	}

	return 0;
}

 

 

 

처음에 명령어를 string으로 이어붙여서 다 저장했다가, 시간이 어마어마하게 걸려버렸다.

// bad example

string dslr = "DSLR";
queue<pair<int, string>> q;
...

while (!q.empty())
{
	int n = q.front().first;
	string ops = q.front().second;
	...

		if (!visit[next])
		{
			visit[next] = true;
			q.push({ next, ops + dslr[i] });
		}

 

 

 

시간 문제를 해결하기 위해서,

1. 방문체크 배열 2. 이전 인덱스 배열 3. 명령어 배열

이렇게 3개의 배열을 만들어주는게 좋다.

 

그러면 각각의 인덱스에 도착할 때에 수행한 명령어를 한 글자씩만 저장할 수 있다.

마지막 end숫자에 도착하면, 

이전 인덱스 배열을 활용해 역으로 출력해주면 된다.

int bf[MOD];
char ops[MOD];

...

// end숫자부터 start숫자까지 역추적해서 op출력
void print(int n)
{
	if (bf[n] == -1)
	{
		return;
	}

	print(bf[n]);

	cout << ops[n];
}