백준 9019번: DSLR

[문제 링크]

9019번: DSLR

---

간단한 문제처럼 보였는데 고려해줘야 할 점이 많은 문제였다.

 

다른 bfs 문제들을 풀듯이 D,S,L,R 4가지 경우에 대해 탐색하면서 string에 추가해주는 방식으로 구현했는데 메모리초과에 시간초과에 난리가 났다.

 

원인을 찾아보니 string 컨테이너의 경우 문자를 추가하는 연산이나 복사본을 큐에 집어넣는 연산에 있어 많은 시간이 필요하다고 한다.

따라서 bfs 탐색을 하면서 방문체크 대신 방문한 숫자 인덱스에 만들기 전 숫자와 어떤 버튼으로 만들었는지 정보를 원소로 담았다.

그다음 목표 숫자 B에서부터 역으로 추적하면서 어떤 버튼을 눌렀는지 vector에 담은 다음 역순으로 출력하도록 구현하였다.

---

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<pair<int, char>> visited(10000);

int calculate(int num, char type) {
	switch (type) {
	case 'D':
		num = (num * 2) % 10000;
		break;

	case 'S':
		if (num == 0) num = 9999;
		else num -= 1;
		break;

	case 'L':
		num = (num % 1000) * 10 + (num / 1000);
		break;

	case 'R':
		num = (num % 10) * 1000 + (num / 10);
		break;
	}

	return num;
}

void Queue_push(queue<int>& q, int num, char type) {
	int nextNum = calculate(num, type);
	if (visited[nextNum].first == -1) {
		visited[nextNum].first = num;
		visited[nextNum].second = type;
		q.push(nextNum);
	}
}

void bfs(int A, int B) {
	visited = vector<pair<int, char>>(10000, { -1,-1 });
	queue<int> q;
	q.push(A);
	visited[A] = { -1, -1 };

	while (!q.empty()) {
		int hereNum = q.front();
		q.pop();

		if (hereNum == B) return;

		Queue_push(q, hereNum, 'D');
		Queue_push(q, hereNum, 'S');
		Queue_push(q, hereNum, 'L');
		Queue_push(q, hereNum, 'R');
		
	}
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--) {
		int A, B;
		cin >> A >> B;
		bfs(A, B);

		vector<char> result;
		int idx = B;
		while (idx != A) {
			result.push_back(visited[idx].second);
			idx = visited[idx].first;
		}
		
		int len = result.size();
		for (int i = len; i >= 0; i--)
			cout << result[i];
		cout << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 167 day