BOJ 9019(DSLR)

풀이

- BFS 문제 D,S,L,R 명령어 별로 경우의 수를 나눠 큐에 담고 B를 만나면 break로 빠져 나오면 된다.

 

고찰

- '레지스터 결과'를 보고 '명령어'를 출력해야 하므로 struct Reg를 큐에 담도록 한다.

- '명령어'는 string을 이용하면 '+' 오퍼레이터로 간단하게 구현이 가능하다.

- visited[10000] 배열을 두어 시작점과, 중간 숫자 결과는 방문 처리 한다!! (그렇지 않으면, 시간초과 난다)

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int d(int a) { 
	return (a * 2) % 10000; 
}
int s(int a) {
	if (a == 0)
		a = 9999;
	else
		a -= 1;
	return a;
}
int l(int a) {
	//int d1 = a / 1000;
	//a -= d1 * 1000;
	//a *= 10;
	//a += d1;
	a = (a % 1000) * 10 + (a / 1000);
	return a;
}
int r(int a) {
	int d4 = a % 10;
	a /= 10;
	a += d4 * 1000;
	return a;
}
//명령어 최대 갯수는??

struct Reg{
	int val;
	//char order[4];
	//deque<char> order;
	string order;
};

bool visited[10000];

void bfs(int A, int B) {
	memset(visited, false, sizeof(visited));

	queue<Reg> qu;
	Reg reg = { A, ""};
	qu.push(reg);
	visited[A] = true;
	while (!qu.empty()) {
		int cVal = qu.front().val;
		//deque<char> cV;
		//for (int i = 0; i < qu.front().order.size(); i++)
		//	cV.push_back(qu.front().order[i]);
		string cV = qu.front().order;
		qu.pop();

		if (cVal == B) {
			for (int i = 0; i < cV.size(); i++)
				cout << cV[i];
			//cout << cV << '\n';
			cout << '\n';
			break;
		}
		int nx = d(cVal);
		if (!visited[nx]) {
			visited[nx] = true;
			//cV.push_back('D'); qu.push({ nx, cV }); cV.pop_back();
			qu.push({ nx, cV +"D"});
		}
		nx = s(cVal);
		if (!visited[nx]) {
			visited[nx] = true;
			//cV.push_back('S'); qu.push({ nx, cV }); cV.pop_back();
			qu.push({ nx, cV + "S" });
		}
		
		nx = l(cVal);
		if (!visited[nx]) {
			visited[nx] = true;
			//cV.push_back('L'); qu.push({ nx, cV }); cV.pop_back();
			qu.push({ nx, cV + "L" });
		}

		nx = r(cVal);
		if (!visited[nx]) {
			visited[nx] = true;
			//cV.push_back('R'); qu.push({ nx, cV }); cV.pop_back();
			qu.push({ nx, cV + "R" });
		}
	}
	return;
}

int main() {
	int t;  cin >> t;
	int A, B;
	while (t--) {
		cin >> A >> B;
		bfs(A, B);
	}
	return 0;
}

 

 

---

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

9019번: DSLR