[C++] 백준 9019: DSLR

안녕하세요 오늘 풀어볼 문제는 백준 DSLR 입니다.

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

 

저는 문제를 두 가지 작은 문제로 나누었어요.

1. 각 연산(DSLR)의 구현

2. 실제 연산을 수행하면서 최소한의 연산 횟수를 탐색

 

1. 각 연산(DSLR)의 구현

이 문제는 어렵지 않습니다.

// D
int d = (n * 2) % 10000;

// S
int s = (n - 1) >= 0 ? (n - 1) : 9999;

// L
int l = (n % 1000) * 10 + (n / 1000);

// R
int r = (n % 10) * 1000 + (n / 10);

 

2. 실제 연산을 수행하면서 최소한의 연산 횟수를 탐색

DFS로 접근을 해볼게요.

1000을 1로 만드는 경우는 'RRR'과 'L' 두 가지가 생각나네요.

1을 1000으로 만드는 경우는 'LLL'과 'R' 두 가지가 생각납니다.

 

연산의 우선순위를 어떻게 정의해야 할까요?

L과 R 사이에 상하 관계가 생긴다면 '최소한의 횟수'라는 조건을 만족할 수 없습니다.

D와 S도 마찬가지구요.

D, S와 L, R 간의 우선순위는 어떻게 정의해야 할까요?

 

이 문제는 BFS 문제입니다.

BFS 알고리즘은 큐에 삽입된 요소들의 크기가 오름차순임이 보장되기 때문에 '최소한'의 조건을 만족하겠네요.

우선순위를 고려할 필요도 없습니다.

 

BFS 흐름을 의사코드로 표현해볼게요.

while (queue is not empty) {
	if (current number equals to B) {
    	print current operators;
    }
    
	for (each operators in DSLR) {
    	tmp = operator(current number)
    	if (tmp is never visited) {
        	push tmp in queue;
            check tmp is visited;
        }
    }
}

 

 

아래는 코드 전문

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int T;
bool visited[10001];

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

	cin >> T;

	while (T--) {
		memset(visited, false, sizeof(visited));
		queue<pair<int, string>> q;
		
		int A, B;
		cin >> A >> B;
		
		q.push({ A,"" });
		visited[A] = true;

		while (!q.empty()) {
			auto p = q.front(); q.pop();
			int n = p.first;
			string cmd = p.second;

			if (n == B) {
				cout << cmd << '\n';
				break;
			}

			int t = (n * 2) % 10000;
			if (!visited[t]) {
				q.push({ t,cmd + 'D' });
				visited[t] = true;
			}

			t = (n - 1) >= 0 ? (n - 1) : 9999;
			if (!visited[t]) {
				q.push({ t,cmd + 'S' });
				visited[t] = true;
			}

			t = (n % 1000) * 10 + (n / 1000);
			if (!visited[t]) {
				q.push({ t,cmd + 'L' });
				visited[t] = true;
			}

			t = (n % 10) * 1000 + (n / 10);
			if (!visited[t]) {
				q.push({ t,cmd + 'R' });
				visited[t] = true;
			}
		}
	}
}