BaekJoon 9019 DSLR

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

소스결과 2128 KB 4712 ms

출처 Baekjoon, ACM-ICPC

언어 C++ 17

분류 BFS

 

설명

네 개의 명령어가 있는 계산기를 사용해 시작값이 목표값 까지 가는 최단 과정을 요구하는 문제

 

4가지의 연산 경로 (D S L R)가 존재하고, 현재 결과를 저장 해야하며 최소한의 명령어를 생성 해야 한다.

Brute Force로 얼핏 가능해 보이지만 질문 게시판을 찾아보니 결론은 힘들다는 내용으로 보인다.

처음 이 문제를 풀었을 때 중복으로 추가하는 부분을 처리 안해줬더니 시간초과가 바로 나왔다.

중복으로 추가하는 부분을 처리해 주니 문제 요구 시간내로 들어왔다.

BFS를 매번 구현하다보니 BFS를 구현하는 내용은 크게 어렵다고 느껴지지 않았지만, 현재까지의 결과를 문자로 저장해야 하는 부분이 애매했다.

char 배열로 처리하려 했으나, 내가 원하는 모습이 나오지 않아 string을 통해 결과를 저장했다.

string의 가장 마지막 자리에 추가하는 내용을 넣는 부분이 연산 시간을 늘리는 overhead를 가져온게 아닐까 하는 생각을 한다.

 

알고리즘

1. 시작값과 목표값을 받는다.

2. 시작 위치를 Queue에 넣고, 시작위치를 이미 추가된 내용으로 처리한다.

3. 현재 시작값을 기준으로 D, S, L, R, 연산 결과와 마지막 연산을 Queue에 넣고, 연산 결과의 값은 이미 추가된 것으로 처리한다.

4. 3번 내용을 반복하면서 목표값에 해당할 떄 까지 반복한다.

5. 목표값까지의 최소 연산을 출력하고, 다음 testCase를 입력 받는다.

 

소스코드

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

using namespace std;

const int MAX = 100;
const int DIGIT_MAX = 10000;
const char DSLR[4] = { 'D', 'S', 'L', 'R' };
int pos = 0;

struct Register {
	string order;
	int res;

	Register() {};
	Register(int res) : res(res) { }
	Register(int res, string order) : res(res), order(order) {}
};

string func(int origin, int target)
{
	string answer;
	bool visited[10000] = {};
	bool isAdded[10000] = {};

	queue<Register> q;

	q.push(Register(origin));
	isAdded[origin] = true;

	while (!q.empty())
	{
		Register cur = q.front();
		q.pop();

		if (visited[cur.res])
			continue;

		visited[cur.res] = true;

		if (cur.res == target)
		{
			answer = cur.order;
			break;
		}
		else
		{
			for (int i = 0; i < 4; i++)
			{
				int res = cur.res;
				switch (DSLR[i])
				{
				case 'D':
					res = ((res * 2) % DIGIT_MAX);
					break;
				case 'S':
					res = (res == 0 ? 9999 : res - 1);
					break;
				case 'L':
					res = ((res * 10) % DIGIT_MAX) + (res / 1000);
					break;
				case 'R':
					res = ((res % 10) * 1000) + (res / 10);
					break;
				default:
					break;
				}
				if (!isAdded[res])
				{
					isAdded[res] = true;
					q.push(Register(res, cur.order + DSLR[i]));
				}
					
			}
		}
	}

	return answer;
}

int main()
{
	int tcc;

	cin >> tcc;

	for (int i = 0; i < tcc; i++)
	{
		int origin, target;
		cin >> origin >> target;

		cout << func(origin, target) << '\n';
	}
	return 0;
}