백준 9019 - DSLR

문제 링크 입니다 https://www.acmicpc.net/problem/9019

9019번: DSLR

BFS 문제입니다.

이렇게 4개의 연산을 할 수 있는 할 수 있는 계산기가 있습니다. 이 계산기에는 0 이상 10000이하의 수를 저장할 수 있다고 할 때 수 A에서 수 B로 바꿀 수 있는 최소 횟수의 연산을 구하는 문제입니다.  

 

각각 연산을 구현한 다음에 BFS를 통해서 A에서 B까지의 연산 과정을 저장하면 됩니다.

 

처음에 vector를 이용해 연산 과정을 저장했지만, 시간 초과가 되었기에 큐를 pair<int, string>으로 만들어 큐에다가 저장하는 식으로 풀었습니다.

 

각각의 D,S,L,R 과정은 코드를 보고 참고해주세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int test_case;
int want, num;
int check[10001];


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int k = 0; k < test_case; k++) {
		queue<pair<int,string>> q;
		cin >> num >> want;
		memset(check, 0, sizeof(check));
		check[num] = 1;
		q.push(make_pair(num, ""));
		
		while (!q.empty()) {
			int x = q.front().first;
			string y = q.front().second;
			int D = (x * 2) % 10000;
			int S = x-1 < 0 ? 9999 : x-1;
			int L = (x % 1000) * 10 + (x / 1000);
			int R = (x%10) * 1000 + (x /10);
			q.pop();

			if (x == want) {
				cout << y;
				break;
			}

			if (check[D] == 0) {
				q.push(make_pair(D,y+"D"));
				check[D] = 1;
			}
			if (check[S] == 0) {
				q.push(make_pair(S, y + "S"));
				check[S] = 1;
			}
			if (check[L] == 0) {
				check[L] = 1;
				q.push(make_pair(L, y + "L"));
			}
			if (check[R] == 0) {
				check[R] = 1;
				q.push(make_pair(R, y + "R"));
			}
		}		
		cout << "\n";
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요