백준 9019번 : DSLR

문제 링크 : www.acmicpc.net/problem/9019

풀이에 참고한 링크 :

www.acmicpc.net/board/view/28910

www.acmicpc.net/board/view/23149

내 풀이1(2021.1.27.) : BFS

#include <iostream>
#include <queue>
#include <string>
#include <string.h>

using namespace std;

string to4(string str) {
	string prefix = "";
	for (int i = 0; i < 4 - str.size(); i++) prefix += "0";
	return prefix + str;
}

string DSLR(char cal, string str) {
	switch (cal) {
	case 'D':
		return to4(to_string(stoi(str) * 2 % 10000));
	case 'S':
		if (str == "0000") return "9999";
		return to4(to_string(stoi(str) - 1));
	case 'L':
		return str.substr(1, 3) + str[0];
	case 'R':
		return str[3] + str.substr(0, 3);
	}
}

char cal[4] = { 'D','S','L','R' };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		queue<pair<string, string>> q;
		string before, after;
		cin >> before >> after;
		before = to4(before);
		after = to4(after);
		int visit[10000];
		memset(visit, 0, sizeof(visit));
		visit[stoi(before)] = 1;
		q.push(make_pair(before, ""));
		bool stop = false;
		while (!q.empty()) {
			pair<string, string> pair = q.front(); q.pop();
			string str = pair.first;
			string dslr = pair.second;
			for (int i = 0; i < 4; i++) {
				string new_str = DSLR(cal[i], str);
				if (new_str == after) {
					cout << dslr + cal[i] << '\n';
					stop = true;
					break;
				}
				if (visit[stoi(new_str)] != 1) {
					visit[stoi(new_str)] = 1;
					q.push(make_pair(new_str, dslr+cal[i]));
				}
			}
			if (stop) break;
		}
	}

	return 0;
}

결과 : 시간 초과

문제점 1) string과 관련된 연산들 stoi, to_string, to4 등이 오래 걸린다. (심지어 순수한 string 자체만으로도 생성 비용과 메타 테이터 등 때문에 char*보다 오래 걸린다.)

문제점 2) queue에 삽입/삭제하는 요소의 메모리 차지 공간이 클수록 연산 시간이 오래 걸린다.

 

내 풀이2(2021.1.27.) :

#include <iostream>
#include <queue>
#include <string>
#include <string.h>

using namespace std;

int DSLR(char cal, int val) {
	switch (cal) {
	case 'D':
		return val * 2 % 10000;
	case 'S':
		if (val == 0) return 9999;
		return val - 1;
	case 'L':
		return val * 10 % 10000 + val * 10 / 10000;
	case 'R':
		return val % 10 * 1000 + val / 10;
	}
}

char cal[4] = { 'D','S','L','R' };

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

	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		queue<int> q;
		int before, after; cin >> before >> after;
		pair<bool, string> visit[10000];
		for (int i = 0; i < 10000; i++) {
			visit[i].first = false;
		}
		
		visit[before].first = true;
		visit[before].second = "";
		q.push(before);

		while (!q.empty()) {
			int val = q.front(); q.pop();
			if (val == after) {
				cout << visit[val].second << '\n';
				break;
			}
			for (int i = 0; i < 4; i++) {
				int new_val = DSLR(cal[i], val);
				if (visit[new_val].first == false) {
					visit[new_val].first = true;
					visit[new_val].second = visit[val].second + cal[i];
					q.push(new_val);
				}
			}
		}
	}

	return 0;
}

결과 : 성공