백준 9019번 : DSLR

문제 접근

---

1. 기본 BFS에서 평범한 좌표 이동 대신에 수식 계산을 대입한 문제로 생각하자.
   
     기본적인 BFS 문제는 주변 좌표의 값을 탐색하는 문제다. 이번 문제는 좌표 탐색 대신에 수식이 주어졌기 때문에, 수를 vertex로, 수식 계산을 하나의 edge로 생각하며 문제를 풀었다.

 

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

9019번: DSLR

 

 

 

문제 코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

	int T, A, B;
	vector<bool> visited(10000);
	queue<pair<int, string>> bfs;

	int cmd_result[5];
	char cmd_text[5] = { '.', 'D', 'S', 'L', 'R' };

	cin >> T;

	while (T--)
	{
		fill(visited.begin(), visited.end(), false);
		while (!bfs.empty()) bfs.pop();

		cin >> A >> B;

		bfs.push(make_pair(A, ""));
		visited[A] = true;

		while (!bfs.empty())
		{
			int source = bfs.front().first;
			string cmd_history = bfs.front().second;

			bfs.pop();

			if (source == B)
			{
				cout << cmd_history << '\n';
				break;
			}

			cmd_result[1] = source * 2 % 10000;
			cmd_result[2] = (source == 0) ? 9999 : source - 1;
			cmd_result[3] = source % 1000 * 10 + source / 1000;
			cmd_result[4] = source % 10 * 1000 + source / 10;


			for (int check = 1; check < 5; ++check)
			{
				if (!visited[cmd_result[check]])
				{
					bfs.push(make_pair(cmd_result[check], cmd_history + cmd_text[check]));
					visited[cmd_result[check]] = true;
				}
			}
		}
	}


	return 0;
}

 

 

 

 

문제 코드 - 개선

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

	int T, A, B, trace;
	string ans;

	vector<int> visited(10000);
	vector<char> ans_cmd(10000);
	queue<int> bfs;

	int cmd_result[5];
	char cmd_text[5] = { '.', 'D', 'S', 'L', 'R' };

	cin >> T;

	while (T--)
	{
		fill(visited.begin(), visited.end(), -1);
		fill(ans_cmd.begin(), ans_cmd.end(), '.');
		while (!bfs.empty()) bfs.pop();

		cin >> A >> B;

		bfs.push(A);


		while (!bfs.empty())
		{
			int source = bfs.front();

			bfs.pop();

			if (source == B)
				break;

			cmd_result[1] = source * 2 % 10000;
			cmd_result[2] = (source == 0) ? 9999 : source - 1;
			cmd_result[3] = source % 1000 * 10 + source / 1000;
			cmd_result[4] = source % 10 * 1000 + source / 10;


			for (int check = 1; check < 5; ++check)
			{
				if (visited[cmd_result[check]] == -1)
				{
					bfs.push(cmd_result[check]);
					visited[cmd_result[check]] = source;
					ans_cmd[cmd_result[check]] = cmd_text[check];
				}
			}
		}

		trace = B;
		ans = "";

		while (trace != A)
		{
			ans += ans_cmd[trace];
			trace = visited[trace];
		}

		reverse(ans.begin(), ans.end());

		cout << ans << '\n';
	}


	return 0;
}

 

    문제를 풀면서 queue에 지나온 모든 경로를 저장하는 게 계속 꺼림칙했다. 결국 기존 코드도 맞긴 했지만, 다른 사람들의 풀이를 보며 한 가지 개선할 수 있는 아이디어를 얻었다.

 

    BFS 알고리즘은 특정 vertex를 처음으로 방문했을 때, visited를 true로 바꾸는 방식이다. 따라서 모든 visited가 true로 바뀌는 순간은 시작점부터 해당 vertex까지의 최단 경로로 도달한 순간임을 의미한다.

 

    그렇기에 visited에 단순히 true가 아닌 어떤 수에서 넘어왔는지, 어떤 명령을 통해 넘어왔는지에 대한 데이터를 기록하면, 추후 목적지에서부터 역산하여 경로를 알 수 있게 된다. 사실 어떤 수에서 넘어왔는지만 최단 경로를 확인해도 알 수 있지만 다시 계산하는 과정을 없애기 위해 어떤 명령으로 넘어왔는지에 대한 데이터도 같이 기록했다. 지금 생각해보니 이럴 거면 모든 경로를 계산에 사용되는 visited에 넣을게 아니라 따로 배열을 만들어 최단 경로에 대해서만 기록했으면 훨씬 효율적이었을 것 같다. 다음부터는 데이터가 필요한 영역을 확실히 구분해서 불필요한 연산이 생기지 않게 해 보자.

 

    글 작성하다가 생각난 고칠 점을 다음부터 적용하기에는 찜찜해서 코드를 수정해 봤다. 결과는 아래와 같은데, visited에 모든 경로를 저장하지 않으니 수행 시간이 극적으로 단축됐고, 최단 경로에 대해서만 명령 문자를 저장하니 수행 시간이 한번 더 소폭 감소했다.

 

    처음에는 시간 복잡도가 크게 달라진 게 없어서, 메모리 사용량이 개선될 거라고 생각했는데 수행 시간이 훨씬 크게 개선이 돼서 신기했다. 이 부분은 한 번 알아봐야 될 것 같다.

 

백준 9019번 : DSLR

 

 

 

느낀 점

---

    알고리즘 레콩키스타 이후, 처음으로 런타임 에러가 났다. 어떤 이유로 런타임 에러가 났는지 알 수라도 있으면 좋을 텐데, IDE에서는 내가 테스트해 본 반례들이 잘 동작하니 다시 한번 맞왜틀을 외쳤다. 그러다가 질문 게시판의 반례를 통해 n이 0일 때, S 연산 쪽에서 off-by-one 에러가 난다는 걸 알게 되어 겨우 겨우 런타임 에러를 해결할 수 있었다.

    알고리즘 레콩키스타를 시작한 지 이제 5일째인데 회복세가 나쁘지 않다. 무엇보다 재미있기도 하고.. 지금처럼만 무리하지 않고 계속 꾸준히 나아가보자.

 

1. 접근 방법이 떠오르면 간단하게라도 정당성 검증을 하자.
   
     접근 방법을 검증하는 습관을 들이지 않으면, 문제 해결과 상관이 없는 시도에 시간을 낭비하게 될 수 있다. 
   
   
2. 문제의 조건에서 제한할 수 있는 부분을 찾고, 이를 통해 해당 문제에서 절대적인 명제를 만들자.
   
     답이 나올 수 있는 영역을 한정한다던가, 입력의 순서 등 제한할 수 있는 부분에서 절대적인 명제를 찾으면, 해당 명제를 기준으로 문제를 조금 더 쉽게 풀 수 있다. 지뢰 찾기나 스도쿠처럼..!
   
   
3. 범위는 신중하게 설정하자.
   
     예전부터 범위를 한 단위씩 잘못 넣어 off-by-one 에러가 나는 일이 잦다. 범위를 신중하게 확인하자. 
   
   
4. 수식은 웬만하면 문제에서 서술하는 방식과 동일하게 맞추자.
   
     이전부터 강조하는 거지만 어쨌든 코드를 보는 건 사람이기에 직관적이지 않은 표현은 좋지 않다. 문제의 서술 방식과 수식을 맞춰 직관적인 이해가 가능하도록 작성해 보자.
   
   
5. 알고리즘 개념에 문제 조건을 대입해 보자.
   
     그냥 알고리즘을 응용하는 거긴 한데, 초반에 문제의 조건과 알고리즘 기본 개념을 연결 짓는 연습을 하면 좋을 것 같다는 생각을 했다.