[알고리즘] 백준 9019번: DSLR (C++), 간결한 생각 (최적화)

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

9019번: DSLR

문제를 읽으면 쉽게 BFS를 떠올릴 수 있다.

하지만, 문제를 풀면서 실수도 하고, 최적화를 생각하지 못해서 많이 틀렸던 문제다.

정리를 하는 이유는 이런 실수가 있었다. 다음부터는 그러지 말자의 의미.

 

[솔루션]

아마 사람들이 좀 많이 헷갈리지 않을까 싶은 부분은

'명령어를 어떻게 저장할 것인가? (구할 것인가?)'

>> 간단하다, pair형 큐를 선언하고 한쪽에는 숫자(int), 다른 한쪽에는 명령어(string)를 넣고, 각각 명령어를 실행할 때마다 string + '명령어'의 형식으로 큐에 push 하고, BFS를 돌리면 풀리는 문제다.

지금 말한 부분을 코드(BFS)로 보면 단번에 이해가 될 것이다.

 

[BFS]

void bfs(int value, int findValue) {
	queue<pair<int, string>> q;
	q.push(make_pair(value, ""));
	visited[value] = 1;
	while (!q.empty()) {
		int front = q.front().first;
		string frontStr = q.front().second;

		if (front == findValue) {
			cout << frontStr;
			return;
		}
		q.pop();

		//D S L R
		int Dvalue = D(front);
		if (!visited[Dvalue]) {
			visited[Dvalue] = 1;
			q.push(make_pair(Dvalue, frontStr + 'D'));
		}
		int Svalue = S(front);
		if (!visited[Svalue]) {
			visited[Svalue] = 1;
			q.push(make_pair(Svalue, frontStr + 'S'));
		}
		int Lvalue = L(front);
		if (!visited[Lvalue]) {
			visited[Lvalue] = 1;
			q.push(make_pair(Lvalue, frontStr + 'L'));
		}
		int Rvalue = R(front);
		if (!visited[Rvalue]) {
			visited[Rvalue] = 1;
			q.push(make_pair(Rvalue, frontStr + 'R'));
		}
	}
}

---

[실수 2가지]

1) L, R 함수의 최적화

이 문제를 풀기 전에 연속으로 문자열 관련 문제를 풀다 보니 L과 R 함수 또한 보자마자 문자열로 구현하려 했었다. 하지만, 이는 시간 초과를 유발했다는 점.

 

[문자열로 구현한 L, R]

int L(int value) {
	string strVal = to_string(value);

	char temp = strVal[0];
	string strResult = strVal.substr(1, strVal.size() - 1);
	strResult += temp;

	if (strResult[0] == 0) {
		reverse(strResult.begin(), strResult.end());
		while (strResult.back() == 0) {
			strResult.pop_back();
		}
		reverse(strResult.begin(), strResult.end());
	}

	return stoi(strResult);
}

int R(int value) {
	string strVal = to_string(value);
	if (strVal.size() < 4) {
		reverse(strVal.begin(), strVal.end());
		while (strVal.size() < 4) {
			strVal += '0';
		}
		reverse(strVal.begin(), strVal.end());
	}
	char temp = strVal.back();
	strVal.pop_back();
	strVal = temp + strVal;

	if (strVal[0] == 0) {
		reverse(strVal.begin(), strVal.end());
		while (strVal.back() == 0) {
			strVal.pop_back();
		}
		reverse(strVal.begin(), strVal.end());
	}

	return stoi(strVal);
}

 

[숫자의 특성을 살려서 구현한 L, R]

int L(int value) {
	int Lvalue = (value % 1000) * 10 + value / 1000;
	return Lvalue;
}

int R(int value) {
	int Rvalue = (value % 10) * 1000 + (value / 10);
	return Rvalue;
}

 

코드 길이부터가 엄청난 차이를 보인다. 다음부터는 이런 실수 하지 말자.

 

2) visited의 잘못된 reset

이 문제 때문에 제일 시간을 잡아먹었었는데 0이 나올 거라는 사실을 인지했으나 reset에서는 문제가 발생하지 않을 거라는 편협된 사고방식 때문에 빨리 발견하지 못했던 거 같다.

>> 제일 민망한 실수인 거 같다.

 

[Before]

void reset() {
	for (int i = 1; i <= 9999; i++) {
		visited[i] = 0;
	}
	return;
}

[After]

void reset() {
	for (int i = 0; i <= 9999; i++) {
		visited[i] = 0;
	}
	return;
}

---

[AC 코드]

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

int T;
bool visited[10000] = { 0, };

int D(int value) {
	value *= 2;
	if (value > 9999) {
		value %= 10000;
	}

	return value;
}

int S(int value) {
	value -= 1;
	if (value < 0) {
		value = 9999;
	}

	return value;
}

int L(int value) {
	int Lvalue = (value % 1000) * 10 + value / 1000;
	return Lvalue;
}

int R(int value) {
	int Rvalue = (value % 10) * 1000 + (value / 10);
	return Rvalue;
}

string bfs(int value, int findValue) {
	string answer;
	queue<pair<int, string>> q;
	q.push(make_pair(value, ""));
	visited[value] = 1;
	while (!q.empty()) {
		int front = q.front().first;
		string frontStr = q.front().second;

		q.pop();

		if (front == findValue) {
			answer = frontStr;
			break;
		}

		//D S L R
		int Dvalue = D(front);
		if (!visited[Dvalue]) {
			visited[Dvalue] = 1;
			q.push(make_pair(Dvalue, frontStr + 'D'));
		}
		int Svalue = S(front);
		if (!visited[Svalue]) {
			visited[Svalue] = 1;
			q.push(make_pair(Svalue, frontStr + 'S'));
		}
		int Lvalue = L(front);
		if (!visited[Lvalue]) {
			visited[Lvalue] = 1;
			q.push(make_pair(Lvalue, frontStr + 'L'));
		}
		int Rvalue = R(front);
		if (!visited[Rvalue]) {
			visited[Rvalue] = 1;
			q.push(make_pair(Rvalue, frontStr + 'R'));
		}
	}
	return answer;
}

void reset() {
	for (int i = 0; i <= 9999; i++) {
		visited[i] = 0;
	}
	return;
}

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

	/*
	int idx;
	cin >> idx;
	cout << L(idx) << ' ' << R(idx);
	return 0;
	*/

	cin >> T;
	int a, b;
	for (int i = 0; i < T; i++) {
		cin >> a >> b;
		cout << bfs(a, b) << '\n';
		reset();
	}

	return 0;
}