[백준 / C++] 9019번: DSLR

 

 

 

 

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

9019번: DSLR

난이도: solved.ac 골드 4

 

알고리즘 분류

그래프 탐색 (BFS)

 

접근 방법

BFS 함수에서 현재 숫자에서 D, S, L, R 연산을 해 큐에 집어 넣는다.

그리고 visited 배열을 통해 방문한 숫자 (0 ~ 9999)를 체크하여 중복된 숫자를 방문하지 않도록 해준다.

 

구현 방법

현재 레지스터의 숫자를 저장할 int 형과 현재까지의 연산과정을 적은 string 형을 pair로 묶어 큐에 사용하였다.

D, S, L, R 연산을 하고나면 그 결과와 각 연산의 알파벳을 현재 큐의 front에 있는 string에 붙인 것을 큐에 push했다.

코드

#include <bits/stdc++.h>
using namespace std;
int visited[10000];
int A, B;
void BFS();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		cin >> A >> B;
		BFS();
		memset(visited, 0, sizeof(visited));
	}
}

void BFS() {
	queue<pair<int, string>> q;
	q.push(make_pair(A, ""));
	visited[A] = 1;
	while (!q.empty()) {
		int num = q.front().first;
		string s = q.front().second;
		if (num == B) {
			cout << s << "\n";
			return;
		}
		q.pop();
		int D, S, L, R;
		// D 연산
		D = (num * 2) % 10000;
		if (!visited[D]) {
			visited[D] = 1;
			q.push(make_pair(D, s + 'D'));
		}
		// S 연산
		S = num - 1;
		if (S == -1) S = 9999;
		if (!visited[S]) {
			visited[S] = 1;
			q.push(make_pair(S, s + 'S'));
		}
		// L 연산
		L = (num * 10) % 10000 + num / 1000;
		if (!visited[L]) {
			visited[L] = 1;
			q.push(make_pair(L, s + 'L'));
		}
		// R 연산
		R = num / 10 + (num % 10) * 1000;
		if (!visited[R]) {
			visited[R] = 1;
			q.push(make_pair(R, s + 'R'));
		}
	}
}

 

성능

코드 제출 결과