개요

백준 9019번: DSLR

• 입력
  프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

• 출력
  A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

접근 방식

1. bfs를 통해 문제를 풀었다.
   기본적으로 백준 16397번: 탈출 문제에서
   버튼을 누른 순서를 출력하라는 옵션이 추가된 느낌이였다.

2. 처음엔 l버튼과 r버튼을 보고 deque 자료구조가 떠올라서,
   bfs의 큐 자료형으로 사용할 calculator라는 구조체를
   현재 숫자를 저장한 deque과, 지금까지 눌러온 버튼 순서를 저장한 vector로 구성했다.

3. 하지만 숫자를 자리마다 deque안에 넣고 다시 deque원소를 하나씩 꺼내서 int형으로 만드는 게 매우 비효율적이였고, deque을 없애고 calculator 구조체를 int형과 vector로만 구성하였다

4. 그 후, 큐를 이용해 bfs구현하며, d,s,l,r버튼을 누를 때, 해당 노드의 버튼vector에
   버튼 이름도 pushback해주도록 구현하였다.

5. 탈출 문제와 std::function 을 이용해 함수 배열을 선언하였다,

//함수 포인터
const function<int(int)> f[4] = {
	//D입력받을 시,
	[](int num) {
		if (num * 2 > 9999) { return num = (num * 2) % 10000; }
		else return num *= 2;
	},
	//S입력받을 시,
	[](int num) {
		if (num == 0) { return 9999; }
		else return num -= 1;
	},
		//L입력받을 시,
	[](int num) {
		int tmp = num / 1000;
		num -=tmp * 1000;
		num = num * 10 + tmp;
		return num;
	},
		//R입력받을 시,
	[](int num) {
		int tmp = num;
		//일의 자리 저장
		int digit1 = num % 10;
		//10으로 나눠줘 일의자리 없애기
		num /= 10;
		//10곱하고 더해주기.
		num += 1000 * digit1;
		return num;
	},


};

코드

#include<iostream>
#include<vector>
#include<queue>
#include<functional>

using namespace std;

int testCases = 0, startNum = 0, goalNum = 0;
int visited[10'001];
char DSLR[4] = { 'D','S','L','R' };

//각 bfs에서 사용되는 답배열이랑 숫자배열 저장하는 구조체
struct calculator {
	int Num;
	vector<char> Ans;
};


//함수 포인터
const function<int(int)> f[4] = {
	//D입력받을 시,
	[](int num) {
		if (num * 2 > 9999) { return num = (num * 2) % 10000; }
		else return num *= 2;
	},
	//S입력받을 시,
	[](int num) {
		if (num == 0) { return 9999; }
		else return num -= 1;
	},
		//L입력받을 시,
	[](int num) {
		int tmp = num / 1000;
		num -=tmp * 1000;
		num = num * 10 + tmp;
		return num;
	},
		//R입력받을 시,
	[](int num) {
		int tmp = num;
		//일의 자리 저장
		int digit1 = num % 10;
		//10으로 나눠줘 일의자리 없애기
		num /= 10;
		//10곱하고 더해주기.
		num += 1000 * digit1;
		return num;
	},


};

void Solution();

void Input() {

	cin >> testCases;
	while (testCases--) {
		//visited 배열 초기화
		fill(&visited[0], &visited[10000], false);
		cin >> startNum >> goalNum;

		Solution();
		if (testCases != 0) cout << '\n';
	}
}

void Solution() {
	//bfs에 사용될 큐
	queue<calculator> q;
	calculator tmpCal;
	//초기 calculator에 startNum값 넣어주고,
	tmpCal.Num = startNum;
	//push해줌
	q.push(tmpCal);
	//시작값 방문 처리
	visited[startNum] = true;

	while (!q.empty()) {
		calculator cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			//각 버튼을 눌렀을 때의 숫자
			int nextA = f[i](cur.Num);
			//숫자가 목표와같다면 출력!
			if (nextA == goalNum) {
				for (auto iter = cur.Ans.begin(); iter != cur.Ans.end(); ++iter) {
					cout << *iter;
				}
				cout << DSLR[i];
				return;
			}
			//범위 나가면 continue
			if (nextA < 0 || nextA >= 10'000) continue;
			//방문한 숫자면 continue
			if (visited[nextA]) continue;
			//방문처리
			visited[nextA] = true;
			//각 버튼값 벡터에 넣어줌
			cur.Ans.push_back(DSLR[i]);
			//큐에 다음 노드로 푸시해줌
			q.push({ nextA,cur.Ans });
			//cur.Ans는 반복문 3번할동안 공유하므로 지금넣어준값 pop해야함.
			cur.Ans.pop_back();
		}
	}
}

int main() {
	//시간초과 안나도록,,
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	Input();
}

문풀후생

이번 문제는 유독 생각할 것이 많았다고 느꼈다.

1. 처음엔 cur.Ans벡터를 큐에 푸시해주고 pop을 안해줬더니,
   dslr버튼 누르는 반복문 4번동안 계속 벡터가 공유되고 값이 4번 푸시되었었다.

2. d버튼 1000으로 나눈 몫인줄 알았다. (10000이다!)

3. L과 R계산을 할 때 네자리수로 이뤄진걸 생각을 못하고
   그냥 숫자로만 생각을 해서 서로 최대자릿수, 1의 자릿수를 넘겨줬다.

   따라서
   0123-> L하면 1230이여야 하는데 231 이런식으로 되고,
   0123-> R하면 3012여야하는데 312이런식으로 구현이 되었다.

   //L입력받을 시,
   	[](int num) {
   		//제일 높은 자릿수의 숫자
   		int tmp = num;
   		//자릿수
   		int cnt = 1;
   		while (tmp/10 != 0) {
   			tmp /= 10;
   			cnt*=10;
   		}
   		//제일 윗자리수 빼준 후
   		num -= tmp * cnt;
   		//숫자 10곱한후 tmp넣어줌.
   		num = num * 10 + tmp;
   		return num;
   	},
   	//R입력받을 시,
   	[](int num) {
   		int tmp = num;
   		//자릿수
   		int cnt = 1;
   		while (tmp / 10 != 0) {
   			tmp /= 10;
   			cnt *= 10;
   		}
   		//일의 자리 저장
   		int digit1 = num % 10;
   		//10으로 나눠줘 일의자리 없애기
   		num /= 10;
   		//10곱하고 더해주기.
   		num = num +cnt*digit1;
   		return num;
   	},

   이런식으로 접근을 했었다.

4. visited 배열 반복문마다 초기화 안 해줬다.

5. 1번의 실수로 인해 bfs안의 dslr버튼 각각 누르는 반복문에서
   새로 벡터를 만들어서 해당 벡터에 cur.Ans를 할당해주는 식으로 짰더니
   반복문마다 벡터원소를 다 넣어주는 과정으로 인해
   벡터 크기가 커지면 커질수록 할당하는과정에서 너무 오래걸렸다.

   따라서 생각해낸게 cur.ans를 복사하지말고 해당 벡터를 쓰되,
   큐에 push한 후 방금 push한 원소를 pop해주는 식으로 짰더니, 시간통과하였다.