[백준][9019] DSLR

이 포스트는 백준 사이트의 DSLR 문제 풀이입니다.

문제

해결 과정

이 문제는 4가지 연산에 따른 결과를 BFS를 활용해 반복적으로 수행하며 정답을 구할 수 있습니다.

첫 번째 시도에서는 주어진 숫자(start)를 문자열을 활용하여 4가지 연산을 수행하고자 하였습니다. 그러나 이러한 방법은 시작 숫자가 1 이고 목표한 숫자가 1000 이라면 출력값은 R 이 나와야 하지만
실제 출력된 값은 ‘DDSDDSRS’ 으로 잘못된 값이 출력되었습니다.

첫 번째 시도 (실패)

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int T, start, goal;
bool visited[10'000];

string BFS(int in);


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> T;
	while(T--)
	{
        fill(visited, visited + 10'000, false);
		cin >> start >> goal;
		printf("%s\n", BFS(start).c_str());
	}
	return 0;
}


string BFS(int in)
{
	queue<pair<string, int>> q;
	q.push(make_pair("", in));
	visited[in] = true;

	while (false == q.empty())
	{
		string curr_cal = q.front().first;
		int curr_num = q.front().second;
		q.pop();

		if (goal == curr_num)
			return curr_cal;

		if (curr_num >= 10)
		{
			int l_index = to_string(curr_num).front() == '0' ? curr_num * 10 : (curr_num % 1000 * 10 + curr_num / 1000);
			if (false == visited[l_index])
			{
				visited[l_index] = true;
				q.push(make_pair(curr_cal + "L", l_index));
			}

			int r_index = to_string(curr_num).back() == '0' ? curr_num / 10 : (curr_num / 10 + 1000 * (curr_num % 10));
			if (false == visited[r_index])
			{
				visited[r_index] = true;
				q.push(make_pair(curr_cal + "R", r_index));
			}
		}

		int d_index = curr_num * 2 > 9999 ? (curr_num * 2 % 10000) : curr_num * 2;
		if (false == visited[d_index])
		{
			visited[d_index] = true;
			q.push(make_pair(curr_cal + "D", d_index));
		}

		int s_index = curr_num == 0 ? 9999 : curr_num - 1;
		if (false == visited[s_index])
		{
			visited[s_index] = true;
			q.push(make_pair(curr_cal + "S", s_index));
		}
	}
}

두 번째 시도 (성공)

두 번째 시도에는 숫자의 자리수가 제한되어 있음을 활용하여
삼항 연산자 대신 나눗셈 연산을 활용해 수식을 정리하여 원하는 출력값이 나오도록 수정하였습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BFS(vector<bool> visited, int start, int goal);


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

    int T;
	cin >> T;
	while(T--) {
        int start, goal;
		cin >> start >> goal;
		BFS(vector<bool>(10001, false), start, goal);
	}

	return 0;
}


void BFS(vector<bool> visited, int start, int goal) {
	queue<pair<string, int>> q;
	q.push(make_pair("", start));
	visited[start] = true;

	while (false == q.empty())
	{
		string curr_cal = q.front().first;
		int curr_num = q.front().second;

		if (goal == curr_num) {
			cout << curr_cal << '\n';
			return;
		}

		q.pop();

		int l_index = (curr_num * 10 + curr_num / 1000) % 10000;
		if (false == visited[l_index]) {
			visited[l_index] = true;
			q.push(make_pair(curr_cal + "L", l_index));
		}

		int r_index = (curr_num / 10 + 1000 * (curr_num % 10));
		if (false == visited[r_index]) {
			visited[r_index] = true;
			q.push(make_pair(curr_cal + "R", r_index));
		}

		int d_index = curr_num * 2 > 9999 ? (curr_num * 2 % 10000) : curr_num * 2;
		if (false == visited[d_index]) {
			visited[d_index] = true;
			q.push(make_pair(curr_cal + "D", d_index));
		}

		int s_index = curr_num == 0 ? 9999 : curr_num - 1;
		if (false == visited[s_index]) {
			visited[s_index] = true;
			q.push(make_pair(curr_cal + "S", s_index));
		}
	}
}

실행 결과