백준 9012 : DSLR
https://www.acmicpc.net/problem/9019
1. 접근
- "최소한"의 명령어를 생성한다고 했으므로 최솟값을 구해야 하는데, DFS는 한 길로 쭉 파기 때문에 최솟값, 최댓값을 구하는 문제와는 거리가 멀다.
=> 한번에 한 단계씩 진행하면서, 원하는 값이 나오자마자 바로 종료하게되는 BFS가 최대,최소와 어울리는 경로 탐색 방법이다. - L과 R의 결과가 무조건 4자리가 나와야 하므로, 굳이 string을 이용할 필요가 없다.(어차피 무조건 4자리씩 확인해야하므로.) => 평소와 같이 숫자로만 접근했다
- BFS 경로탐색을 했을 때, 가장 빨리 목표값을 찾는 건 어렵지 않다.
★ 그 값으로 어떻게 가야할지를 아는 것이 어렵다.
=> BT 배열에 (이전값, dslr값) pair를 넣고 마지막에 그 값을 역으로 추적한다.
~~=> BT 배열에 각 값의 이전 값을 놓고, 직접 값을 구해 백트랙킹해볼까 했으나.. 2000인 경우, 10002를 해서 2000이 되었는지, 60002을 해서 2000이 나왔는지 알 수 없게 되어 더 복잡해졌다. ~~
2. 반례
1
0 1000
SDDLDSLDRDDD
https://www.acmicpc.net/board/view/65714
3
1 10
775 5421
2784 9034
Output
L
SSSSDL
DSLSLDLL
https://hackids.tistory.com/88
3. 나의 풀이
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
bool visited[10001];
pair<int,int> BT[10001];
char outDSLR[5] = {'0', 'D','S','L','R' };
int a,b;
vector<char> path;
int moveLeft(int val) {
int num[4];
for (int i = 3; i >=0; i--) {
num[i] = val % 10;
val /= 10;
}
for (int i = 0; i < 3; i++) {
swap(num[i], num[i + 1]);
}
int ret = num[0];
for (int i = 1; i < 4; i++) {
ret *= 10;
ret += num[i];
}
//cout << ret << "\n";
return ret;
}
int moveRight(int val) {
int num[4];
for (int i = 3; i >= 0; i--) {
num[i] = val % 10;
val /= 10;
}
for (int i = 3; i >0; i--) {
swap(num[i], num[i - 1]);
}
int ret = num[0];
for (int i = 1; i < 4; i++) {
ret *= 10;
ret += num[i];
}
//cout << ret << "\n";
return ret;
}
void BFS(int start) {
queue<int> q;
q.push(start);
BT[start]=make_pair(start,0);
visited[start] = true;
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == b) {
return;
}
int dslr[5];
dslr[1] = (now * 2) % 10000;
dslr[2] =now- 1;
if (dslr[2] < 0) dslr[2] = 9999;
dslr[3] = moveLeft(now);
dslr[4] = moveRight(now);
for (int i = 1; i < 5; i++) {
if (!visited[dslr[i]]) {
visited[dslr[i]]=true;
BT[dslr[i]]=make_pair(now,i);
q.push(dslr[i]);
}
}
}
}
void backtracking(int start) {
if (start == a) return;
path.push_back(outDSLR[BT[start].second]);
backtracking(BT[start].first);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
for(int i=0;i<t;i++){
cin >> a>>b;
memset(visited, false, sizeof(visited));
path.clear();
BFS(a);
backtracking(b);
for (int i = path.size() - 1; i >= 0; i--) {
cout << path[i];
}
cout << "\n";
}
return 0;
}
BFS만 떠올렸다면 방향을 잡기는 쉬웠겠지만 경로 출력하게하는부분이 어려웠다..
Author And Source
이 문제에 관하여(백준 9012 : DSLR), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongopo/백준-9012-DSLR저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)