백준 9019 DSLR (c++) : 피너클

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

9019번: DSLR

 

 

bfs문제다. bfs는 너비 우선 탐색으로 시작 정점에서 가까운 정점들을 우선으로 탐색하는 그래프 알고리즘이다.

문제에서는 총 범위가 10000이고 특정 정점까지의 최소 명령어를 필요로 하는걸 보고 유추할수있다.

 

우선 D, S, L, R을 먼저 구현한다.

int D(int n) {
	int num = n * 2;
	if (num >= 10000) return num % 10000;
	else return num;
}

정수를 전달받고 정수에 2를 곱한뒤 만약 10000보다 크면 10000으로 나눈 나머지 값을, 작으면 곱한수를 리턴한다.

int S(int n) {
	int num = n - 1;
	if (n == 0) return 9999;
	else return num;
}

정수를 전달받고 1을 뺀뒤 뺀 수가 0이면 9999를, 아니면 뺀 수를 그대로 리턴한다.

int L(int n) {
	int num = n % 1000;
	return num * 10 + n / 1000;
}

 

 

여기서 중요한건 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4이라는 것이다. 1은 그냥 1이 아닌 0001이라는 뜻이다.

만약 1을 L에 집어넣으면 1 그대로 나오는 것이 아닌 0001을 L에 집어넣은 0010이 나와야 한다.

위의 코드에 예시로 1234가 들어간다고 생각해보자.

int num에는 1234의 1000의 자리를 제외한 값들이 들어간다. (234)

그후 1234의 1000의 자리를 제외한 값에 10을 곱하고 (2340) 1234를 1000으로 나눈 값(1)을 더한수를 리턴한다. 

다른 예시로 0023이 들어왔다고 생각해보자

int num에는 0023의 1000의 자리를 제외한 값들이 들어간다. (023)

그후 0023의 1000의 자리를 제외한 값에 10을 곱하고 (0230) 0023를 1000으로 나눈 값(0)을 더한수를 리턴한다. 

그럼 1234의 리턴값은 2341이 되고 0023의 리턴값은 0230이 된다.

int R(int n) {
	int num = n / 10;
	return (n % 10) * 1000 + num;
}

R도 같은 맥락이다. 1234가 들어간다고 생각해보자.

int num에는 1234를 10으로 나눈 값 (123) 이 들어간다.

그후 1234를 10으로 나눈 나머지(4)에 1000을 곱하고 (4000) num을 더한 값 (4123)을 리턴한다.

다른 예시로 0023이 들어왔다고 생각해보자.

int num에는 0023를 10으로 나눈 값 (002) 이 들어간다.

그후 0023를 10으로 나눈 나머지(3)에 1000을 곱하고 (3000) num을 더한 값 (3002)을 리턴한다.

 

이제 bfs를 구현할 차례이다.

void bfs(int first, int target) {
	for (int i = 0; i <= 10000; i++) visited[i] = false;
	queue<pair<int, string>> q;
	visited[first] = true;
	q.push({ first, "" });

first에는 초기값이 들어오고 target은 목표값이 들어온다.

for(int i = 0; i <= 10000; i++) visited[i] = false; 에서 visited는 앞으로 변형될 수가 이전에 나온 수인지를

확인하는 방법이다. 3번째에 나온수를 5번째에서 발견한다 해도 최소한의 명령어를 찾는 것이 목표이기 때문에

5번째에 발견한 값을 사용할 필요가 없다.

 

bfs에서는 queue를 사용한다. queue는 들어온 값 순서대로 나오는 자료구조이다. 

1, 2, 3, 4가 들어오면 순서대로 1, 2, 3, 4가 출력된다. 이번 bfs에서는 pair<int, string>으로 큐를 선언한다.

int자리에는 현재 값이 어느 값인지, string에는 지금까지 어떤 명령어를 사용했는지가 선언될것이다.

시작전에 초기값은 처음에 방문한 상태이니 visited에 체크해주고 큐에 초기값과 아무것도 없는 명령어를 넣어준다.

while (!q.empty()) {
	int now = q.front().first;
	string command = q.front().second;
	q.pop();

	if (now == target) {
		cout << command << "\n";
		return;
	}

큐에 값이 하나도 안들어있는 상태가 될때까지 반복문을 돌린다.

int now에는 큐에 들어있는 현재 값이 들어간다.

string command에는 큐에 들어있는 현재 값이 되기까지 사용된 명령어들이 들어간다.

그후 사용한 큐 값은 pop으로 없엔다.

만약 현재 값이 target과 같다면 사용된 명령어를 출력한뒤 함수를 종료시킨다.

int next_num;
next_num = D(now);
if (!visited[next_num]) {
	q.push({ next_num, command + "D" });
	visited[next_num] = true;
}
next_num = S(now);
if (!visited[next_num]) {
	q.push({ next_num, command + "S" });
	visited[next_num] = true;
}
next_num = L(now);
if (!visited[next_num]) {
	q.push({ next_num, command + "L" });
	visited[next_num] = true;
}
next_num = R(now);
if (!visited[next_num]) {
	q.push({ next_num, command + "R" });
	visited[next_num] = true;
}

int next_num에는 다음 값이 들어갈것이다.

next_num에 D(now)를 통해 현재값에 D명령어를 실행한 값을 저장한다.

만약 next_num이 현재까지 나온적이 없는 수라면 큐에 next_num과 현재까지 사용된 명령어 + D를 삽입한다.

그후 visited[next_num]를 true로 만들어 후에 다시 사용되는걸 방지한다.

이 과정을 S, L, R 모두 한번씩 하면 bfs는 끝이다.

 

다음은 전체 코드다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

bool visited[10001];

int D(int n) {
	int num = n * 2;
	if (num >= 10000) return num % 10000;
	else return num;
}
int S(int n) {
	int num = n - 1;
	if (n == 0) return 9999;
	else return num;
}
int L(int n) {
	int num = n % 1000;
	return num * 10 + n / 1000;
}
int R(int n) {
	int num = n / 10;
	return (n % 10) * 1000 + num;
}

void bfs(int first, int target) {
	for (int i = 0; i <= 10000; i++) visited[i] = false;
	queue<pair<int, string>> q;
	visited[first] = true;
	q.push({ first, "" });
	while (!q.empty()) {
		int now = q.front().first;
		string command = q.front().second;
		q.pop();

		if (now == target) {
			cout << command << "\n";
			return;
		}

		int next_num;
		next_num = D(now);

		if (!visited[next_num]) {
			q.push({ next_num, command + "D" });
			visited[next_num] = true;
		}
		next_num = S(now);

		if (!visited[next_num]) {
			q.push({ next_num, command + "S" });
			visited[next_num] = true;
		}
		next_num = L(now);

		if (!visited[next_num]) {
			q.push({ next_num, command + "L" });
			visited[next_num] = true;
		}
		next_num = R(now);

		if (!visited[next_num]) {
			q.push({ next_num, command + "R" });
			visited[next_num] = true;
		}
	}
}

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

	int n, a, b;
	cin >> n;
	while (n-- > 0) {
		cin >> a >> b;
		bfs(a, b);
	}
}