백준 9019(DSLR)

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

9019번: DSLR

BFS에 대해서 좀 더 생각하게끔 해주었던 문제. 

 

앞서 풀었던 치즈같이 queue 두 개를 이용해서 총 몇번의 횟수가 필요한지 구하려고 했었다. 하지만 문제는 문제에서 요구하는 바가 횟수가 아닌 경로였고, 경로를 구하려면 재귀의 방식이 필요하지 않을까 생각을 하였다. 

 

재귀로 경로를 출력하기에 더 편리하게 느껴졌다. 경험이 있어서 그런지 

그래서 재귀와 bfs를 동시에 사용하면 어떨까 해서 생각을 계속 해보다가 아무리 해도 이 문제에서 재귀형식으로 계속해서 함수를 호출하려고 하면 종료조건이 애매해진다는 사실을 알았다. 

 

경로를 어떻게 저장할까. 결국 구글링하였고, 문제의 핵심을 몰랐다는 걸 알게되었다.

 

이 문제의 핵심은 한 번 지나간 곳은 다시 지나가지 않는다. 필요가 없다는 것이다. 

 

bfs의 특성상 가장 얕은 깊이부터 깊게 들어간다. 따라서 먼저 그 숫자를 찾았다면 후에 찾는 숫자보다 더 적거나 같은 연산횟수로 도달한 수가 된다. 

 

그래서 우리는 해당 index에 경로를 저장할 수 있게 되고, 그렇게 저장한 경로가 결국에 원하는 답이 되는 것이다. 

 

경로의 저장방법은 vector<string> str 으로 하였다. 

 

str[index] 의 값에 그 전에 거친 str[before]값을 합친다. 이 때 index값이 되기 위해 필요했던 D,S,L,R 중 하나를 더해서 경로를 완성한다. 

 

str[index] = str[before] + "D" or "S" or "L" or "R" ; 

 

경로의 저장은 이렇다. 

 

나머지는 그냥 평범한 bfs의 형식이다. queue에 담아서, queue가 빌때까지(가능한 모든 경로를 탐색할때까지) 원하는 값을 찾으면 원하는 값을 출력하고 종료. 

 

bfs를 이해하는데 정말 중요한 문제라고 생각한다.

 

그리고 또 함수안에 vector나 bool 변수들을 선언해서 따로 초기화할 필요가 없게 만드는 것도 스킬인것 같다. 

#include<iostream>
#include<queue>
#include<utility>
#include<string>
using namespace std;
#define MAX 10001

queue<int> q;
int T, A, B, tmp, nxt;

int rshift(int num) {
	int d1 = num / 1000;
	num -= d1 * 1000;
	int d2 = num / 100;
	num -= d2 * 100;
	int d3 = num / 10;
	num -= d3 * 10;
	int d4 = num;

	int n = ((d4 * 10 + d1) * 10 + d2) * 10 + d3;
	return n;
}

int lshift(int num) {
	int d1 = num / 1000;
	num -= d1 * 1000;
	int d2 = num / 100;
	num -= d2 * 100;
	int d3 = num / 10;
	num -= d3 * 10;
	int d4 = num;

	int n = ((d2 * 10 + d3) * 10 + d4) * 10 + d1;
	return n;
}

void solve() {
	bool visited[MAX] = { false };
	vector<string> str(MAX);
	str[A] = "";
	visited[A] = true;
	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		nxt = (tmp * 2) % 10000;
		if (!visited[nxt]) {
			visited[nxt] = true;
			q.push(nxt);
			str[nxt] = str[tmp] + "D";
			if (nxt == B) {
				cout << str[nxt] << "\n";
				return;
			}
		}
		if (tmp == 0) {
			if (!visited[9999]) {
				visited[9999] = true;
				q.push(9999);
				str[9999] = str[tmp] + "S";
				if (9999 == B) {
					cout << str[9999] << "\n";
					return;
				}

			}
		}
		nxt = tmp - 1;
		if (tmp > 0 && !visited[nxt]) {
			visited[nxt] = true;
			q.push(nxt);
			str[nxt] = str[tmp] + "S";
			if (nxt == B) {
				cout << str[nxt] << "\n";
				return;
			}

		}
		nxt = lshift(tmp);
		if (!visited[nxt]) {
			visited[nxt] = true;
			q.push(nxt);
			str[nxt] = str[tmp] + "L";
			if (nxt == B) {
				cout << str[nxt] << "\n";
				return;
			}
		}
		nxt = rshift(tmp);
		if (!visited[nxt]) {
			visited[nxt] = true;
			q.push(nxt);
			str[nxt] = str[tmp] + "R";
			if (nxt == B) {
				cout << str[nxt] << "\n";
				return;
			}
		}

	}

}

int main() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> A >> B;
		q.push(A);
		solve();
		while (!q.empty())
			q.pop();
	}
}