백준9019 - DSLR

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

9019번: DSLR

단순 BFS 문제였다. 현재 있는 경로에서 숫자들을 하나씩 탐색한 결과를 저장해두다가 내가 찾는 숫자가 나오면 종료하면 된다. BFS를 사용하니 방문한 곳은 재방문하지 않기 때문에 효율적인 탐색 결과나 나온다.

 

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

int n;
int num1, num2;


void bfs() {
	queue <int> q; //탐색한 결과를 저장하는 공간
	bool visit[10000]; //방문 여부 저장
	string res[10000]; //방문한 결과들을 저장
	int change; //현재 D,S,L,R을 한 결과

	fill(&visit[0], &visit[10000], false); //모든 공간을 미방문 처리
	
	//제일 처음 숫자를 방문처리하고 탐색한 결과에 저장
	q.push(num1);
	visit[num1] = true;
	
	while (!q.empty()) {
		int temp = q.front();

		q.pop();

		if (temp == num2) {
			cout << res[temp] << '\n';
		}

		//D
		change = temp * 2;
		if (change > 9999) {
			change = change % 10000;
		}
		if (!visit[change]) {
			q.push(change);
			res[change] = res[temp] + 'D';
			visit[change] = true;
		}

		//S
		change = temp - 1;
		if (temp == 0) {
			change = 9999;
		}
		if (!visit[change]) {
			q.push(change);
			res[change] = res[temp] + 'S';
			visit[change] = true;
		}

		//L
		change = (temp % 1000) * 10 + temp / 1000;
		if (!visit[change]) {
			q.push(change);
			res[change] = res[temp] + 'L';
			visit[change] = true;
		}

		//R
		change = (temp % 10) * 1000 + (temp / 10);
		if (!visit[change]) {
			q.push(change);
			res[change] = res[temp] + 'R';
			visit[change] = true;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num1 >> num2;
		bfs();
	}
}