[백준 9019번 C/C++] DSLR

 

[백준 9019번 C/C++] DSLR

 

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

9019번: DSLR

---

 

해결전략

 

구현

 

---

 

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

vector<string> ch;

int D(int k){
	return k * 2 % 10000;
}

int S(int k) {
	if (k == 0) return 9999;
	else return k - 1;
}

int L(int k) {
	int temp = k;
	int cnt = 0;
	while (temp >= 10){
		temp /= 10;
		cnt++;
	}
	int firstDigit = k / pow(10, cnt);
	k = (k - firstDigit * pow(10, cnt)) * 10 + firstDigit;

	return k;
}

int R(int k) {
	int lastDigit = k % 10;
	k /= 10;
	int temp = k;
	int cnt = 0;
	while (temp){
		temp /= 10;
		cnt++;
	}
	k = lastDigit * pow(10, cnt) + k;

	return k;
}

void BFS(int x, int goal)
{
	queue<int> Q;
	ch.resize(10000);
	
	Q.push(x);
	ch[x] = "";
	while (!Q.empty())
	{
		if (Q.front() == goal) break;
		int front = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			if (i == 0) {
				if (ch[D(front)] == "") {
					Q.push(D(front));
					ch[D(front)] = ch[front] + 'D';
				}
			}
			else if (i == 1) {
				if (ch[S(front)] == "") {
					Q.push(S(front));
					ch[S(front)] = ch[front] + 'S';
				}
			}
			else if (i == 2) {
				if (ch[L(front)] == "") {
					Q.push(L(front));
					ch[L(front)] = ch[front] + 'L';
				}
			}
			else if (i == 3) {
				if (ch[R(front)] == "") {
					Q.push(R(front));
					ch[R(front)] = ch[front] + 'R';
				}
			}
		}
	}
}

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

	int t;
	cin >> t;
	while (t--){
		int given, goal;
		cin >> given >> goal;

		BFS(given, goal);
		cout << ch[goal];
		cout << "\n";

		ch.clear();
	}

	return 0;
}

 

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

vector<string> ch;

int D(int k){
	return k * 2 % 10000;
}

int S(int k) {
	if (k == 0) return 9999;
	else return k - 1;
}

int L(int k) {
	int firstDigit = k / 1000;
	k = ((k % 1000) * 10) + firstDigit;

	return k;
}

int R(int k) {
	int lastDigit = k % 10;
	k = (lastDigit * 1000) + (k / 10);

	return k;
}

void BFS(int x, int goal)
{
	queue<int> Q;
	ch.resize(10000);
	
	Q.push(x);
	ch[x] = "!"; // 첫 시작 방문체크. 마지막 출력전에 맨앞문자인"!"을 빼고 출력
	while (!Q.empty())
	{
		if (Q.front() == goal) break;
		int front = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			if (i == 0) {
				if (ch[D(front)] == "") {
					Q.push(D(front));
					ch[D(front)] = ch[front] + 'D';
				}
			}
			else if (i == 1) {
				if (ch[S(front)] == "") {
					Q.push(S(front));
					ch[S(front)] = ch[front] + 'S';
				}
			}
			else if (i == 2) {
				if (ch[L(front)] == "") {
					Q.push(L(front));
					ch[L(front)] = ch[front] + 'L';
				}
			}
			else if (i == 3) {
				if (ch[R(front)] == "") {
					Q.push(R(front));
					ch[R(front)] = ch[front] + 'R';
				}
			}
		}
	}
}

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

	int t;
	cin >> t;
	while (t--){
		int given, goal;
		cin >> given >> goal;

		BFS(given, goal);
		cout << ch[goal].substr(1, ch[goal].size() - 1) << "\n";; // 출력전에 맨앞문자인"!"을 빼고 출력

		ch.clear();
	}

	return 0;
}

 

 

---