[백준 9019] DSLR (C++)

A. 문제설명

www.acmicpc.net/problem/9019

9019번: DSLR

문제에 대한 자세한 설명은 링크 참조

 

1. D/S/R/L 4개의 명령을 수행하는 레지스터가 존재

2. 각 명령에 대한 설명은 아래와 같음

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

3. 여기서 서로 다른 두 정수 A, B가 주어졌을 때, A에서 B로 변환하는 최단의 명령조합을 출력할 것

 

B. 접근법

BFS + 극한의 상수 최적화

 

먼저 나는 정말 단순하게 BFS로 각각 D/S/L/R에 대한 함수를 구현하여 접근하였다. 결과는 시간초과였다. 정말 많은 부분을 고민하면서 문제를 해결하려 했으나 실패했다.

 

Rebas 블로그(rebas.kr/764)에서 다시 그 해답을 찾아 알고리즘을 최적화한 결과 통과할 수 있었다. 문제의 핵심은 다음과 같다.

1. D/S/L/R의 연산을 함수호출이 아닌 연산식(Expression)의 배열로 인라인한 것: 여기서 각각의 연산들은 전부 변수에 대한 상수 계산으로 처리되므로 함수 오버헤드를 발생시킬 필요가 없다.

2. 탐색경로는 명령신호와 같이 배열에 넣고 목적지 도달시 B에서 A로 백트랙킹하여 그걸 다시 뒤집음: 경로 배열 map[]과, 명령 배열 cmd[]를 사용하였다.

 

알고리즘이 직관적으로 이해가 잘 안갈 수 있는데 표를 그려 표현하면 아래와 같다.

Ex) A:1234에서 B:3412로 탐색

b	1234	2341	3412
map[b]	-	1234	2341
cmd[b]	-	L	L

표에서 보듯이, b는 처음에 출발점에서 탐사를 시작하여 해당 연산결과가 도달되지 않았을 시, map[]에 목적지->출발지를 연결한다. 그리고 cmd[]에는 해당 연산의 이름을 넣어놓는다.

마지막에 B:3412에 도달성공시, 역순으로 다시 출발지를 찾아나서면 된다.

(map[3412] = 2341, cmd[3412], L) -> (map[2341] = 1234, cmd[2341], L) -> 1234 도달, 종료

 

C. 풀이

1. BFS 큐는 출발점에서 탐사를 시작하여 D/S/L/R 연산을 수행

2. D/S/L/R 연산을 수행한 결과가 도달되지 않았을 시, map[]에 목적지->출발지를 연결, cmd[]에는 해당 연산의 이름을 넣음

3. 목적지 도달시, 다시 역순으로 출발지까지 명령어들을 찾아 벡터에 삽입

4. 마지막으로 벡터를 뒤집고 출력함

 

D. 내 코드

 

	#include <iostream>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int T;
	int map[10000];
	char cmd[10000];
	char C[4] = {'D', 'S', 'L', 'R'};
	void bfs(int x, int y){
	queue<int> bfsQ;
	bfsQ.push(x);
	bool visit[10000] = {0, };
	while(!bfsQ.empty()){
	int b = bfsQ.front();
	bfsQ.pop();
	if(b == y) return;
	int nx[] = {b*2%10000, b-1, b%1000*10+b/1000, b/10+b%10*1000};
	if (nx[1] < 0) nx[1] = 9999;
	for (int i=0; i<4; i++) {
	if (visit[nx[i]]) continue;
	visit[nx[i]] = true;
	map[nx[i]] = b;
	cmd[nx[i]] = C[i];
	bfsQ.push(nx[i]);
	}
	}
	}
	int main(){
	cin >> T;
	int x, y;
	for (int i = 0; i < T; i++) {
	cin >> x >> y;
	bfs(x, y);
	vector<char> v;
	while(map[y] != x){
	v.push_back(cmd[y]);
	y = map[y];
	}
	v.push_back(cmd[y]);
	reverse(v.begin(), v.end());
	for(auto vv:v) cout << vv;
	cout << endl;
	}
	return 0;
	}

view raw dslr.cpp hosted with ❤ by GitHub