백준 9019. DSLR

알고리즘 중급 문제 중 611 - BFS(연습)

DSLR

1. 간단 설명

n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4 일 때

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.

2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.

4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램

2. 예제

A = 1234, B = 3412 라면

1234 ->(L) 2341 ->(L) 3412 혹은 RR로 3412를 만들 수 있음

n의 자릿수로 0 이 포함된 경우에 주의할 것

3. 알고리즘

1. T, A, B를 입력받는다
2. A를 너비우선 탐색을 통해 B가 나오는 최소 경우를 찾는다
	2-1. 초기 작업. A를 큐에 넣고, 해당 수를 만든 경우를 체크해둔다
	2-2. 큐에서 맨 앞을 뺀다
	2-3. 현재 숫자가 B라면, 현재까지 저장된 명령어를 출력하고 종료한다
	2-4. D를 해서 나온 숫자를 방문한 적이 없다면, 해당 수를 방문체크 후, 명령어에 추가한뒤 큐에 넣는다
	2-5. S, L, R 에 대해서도 모두 수행한다. 이를 2-2 ~ 2.5을 반복

필요 변수

• int T
• int A, B
• BFS를 위한 큐
  • 해당 숫자 만든적 있는지 체크할 방문처리용 bool visited[10000] 0~9999
  • BFS 탈출 조건 A == B 일치한다면 현재 커맨드를 출력하기
  • D, S, L, R 중에 하나 넣어보기
  • {만들어진 문자열, 현재 커맨드}를 make_pair 해서 큐에 넣기

4. 소스코드

#include <iostream>
#include <queue>
#include <string>
#include <memory.h>

using namespace std;

int T;
bool visited[10000];

// n = 2n mod 10000
int DDD(int num) {
	return ((num) * 2) % 10000;
}

// n = n-1
int SSS(int num) {
	if (num == 0) 
		return 9999;
	return  num - 1;
}

int LLL(int num) {
	int res = (num % 1000) * 10;
	res += (num / 1000);
	return res;
}

int RRR(int num) {
	int res = (num / 10);
	res += (num % 10) * 1000;
	return res;
}

void BFS(int AAA, int BBB) {
	queue<pair<int, string>> qu;
	qu.push(make_pair(AAA, ""));
	visited[AAA] = true; 

	while (!qu.empty()) {
		pair<int, string> now = qu.front(); // {숫자, 명령어}
		qu.pop();

		if (now.first == BBB) { // 0001과 1을 비교하기 위해 int형 변환
			cout << now.second << '\n';
			return;
		}

		if (visited[DDD(now.first)] == false) {
			visited[DDD(now.first)] = true;
			qu.push(make_pair(DDD(now.first), now.second + "D"));
		}
		if (visited[SSS(now.first)] == false) {
			visited[SSS(now.first)] = true;
			qu.push(make_pair(SSS(now.first), now.second + "S"));
		}
		if (visited[LLL(now.first)] == false) {
			visited[LLL(now.first)] = true;
			qu.push(make_pair(LLL(now.first), now.second + "L"));
		}
		if (visited[RRR(now.first)] == false) {
			visited[RRR(now.first)] = true;
			qu.push(make_pair(RRR(now.first), now.second + "R"));
		}
	}
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> T;
	while (T--) {
		memset(visited, 0, sizeof(visited));
		int A, B;

		cin >> A >> B;

		BFS(A, B);
	}
	return 0;
}

첫 시도에서는 시간 초과가 발생했다

숫자를 편하게 다루기 위해서 DSLR 함수를 string형으로 시도했었는데,

이를 형 변환하는 과정에서 시간초과가 발생한 것으로 보였다.

DSLR 함수를 int형으로 수정한 뒤, 형 변환 과정을 생략하니 무사히 통과했다

아래는 시간초과난 string 함수

// n = 2n mod 10000
string DDD(string num) {
	return to_string((stoi(num) * 2) % 10000);
}

// n = n-1
string SSS(string num) {
	if (num == "0") {
		return "9999";
	}

	return  to_string(stoi(num) - 1);
}

// lotate left
string LLL(string num) {
	string res = "";
	for (int i = 1; i < num.length(); i++) {
		res += num[i];
	}
	res += num[0];
	return res;
}

// lotate right
string RRR(string num) {
	string res = "";
	res += num[num.size() - 1];
	for (int i = 0; i < num.length() - 1; i++) {
		res += num[i];
	}
	return res;
}

void BFS(string AAA, string BBB) {
	queue<pair<string, string>> qu;
	qu.push(make_pair(AAA, ""));
	visited[stoi(AAA)] = true; 

	while (!qu.empty()) {
		pair<string, string> now = qu.front(); // {숫자, 명령어}
		qu.pop();

		if (stoi(now.first) == stoi(BBB)) { // 0001과 1을 비교하기 위해 int형 변환
			cout << now.second << '\n';
			return;
		}

		for (int t = 0; t < 4; t++) {
			string next = "";
			if (t == 0) {
				next = DDD(now.first);
				if (visited[stoi(next)] == true) continue;
				qu.push(make_pair(next, now.second + "D"));
			}
			else if (t == 1) {
				next = SSS(now.first);
				if (visited[stoi(next)] == true) continue;
				qu.push(make_pair(next, now.second + "S"));
			}
			else if (t == 2) {
				next = LLL(now.first);
				if (visited[stoi(next)] == true) continue;
				qu.push(make_pair(next, now.second + "L"));
			}
			else{
				next = RRR(now.first);
				if (visited[stoi(next)] == true) continue;
				qu.push(make_pair(next, now.second + "R"));
			}
			visited[stoi(next)] = true;
		}
	}
}