[ACM-ICPC][BOJ] 9019 - DSLR

안녕하세요.

여행벌입니다.

---

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

9019번: DSLR

[알고리즘설계]

1. A에서 시작해서 명령어 D / S / L / R  을 한 숫자가 아직 방문하지 않은 숫자라면 queue에 담아 가며 B가 나올 때까지 BFS 탐색을 진행한다. 이때, int path[10000], char answer[10001] 을 이용해서 방문 경로를 저장한다.

2. B에서 다시 방문 경로를 역 탐색하며 출력해준다.

#include<iostream>
#include<queue>

using namespace std;

char DSLR[5] = "DSLR";
void BFS(int, int);

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

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int A, B;
		cin >> A >> B;
		BFS(A,B);
	}
}

void BFS(int A, int B) {
	bool check[10000] = {};
	int npath[10000] = {};
	char cpath[10001] = {};
	queue<int> q;
	q.push(A);
	check[A] = true;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		if (x == B) {
			vector<char>answer;
			while (x != A) {
				answer.push_back(cpath[x]);
				x = npath[x];
			}
			int length = (int)answer.size();
			for (int i = 0; i < length; i++)
				cout << answer[length - 1 - i];
			cout << '\n';
			return;
		}
		int list[4] = { (2 * x) % 10000, x - 1, (x % 1000) * 10 + x / 1000, (x % 10) * 1000 + x / 10 };
		if (list[1] < 0)
			list[1] = 9999;
		for (int i = 0; i < 4; i++) {
			if (!check[list[i]]) { // 지금 가려는 곳이 방문한 곳이 아니라면
				q.push(list[i]);
				check[list[i]] = true;
				npath[list[i]] = x;
				cpath[list[i]] = DSLR[i];
			}
		}

	}
}

코드는 간단하지만 구현하는데 정말 고생한 문제입니다...!

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.