💛IV [백준 9019/C++] DSLR

BOJ 문제 보기

1. 문제

A를 B로 바꾸기 위한 최소 연산을 출력하는 문제다. 4자리 숫자를 모두 조회하는데 0000부터 9999까지 총 10000개의 정점이 필요하므로 BFS를 활용해 문제를 해결할 수 있다. (정점의 개수가 많지 않음)

1. D : n * 2
   • num*2 > 9999라면 10000으로 나눈 값의 나머지 적재
2. S : n - 1
   • n=0이라면 9999 적재
3. L : 왼쪽으로 자릿수 이동 (1234 $\rightarrow$ 2341)
4. R : 오른쪽으로 자릿수 이동 (1234 $\rightarrow$ 4123)

---

2. 해결 방법

배열을 만들어 연산 진행 상황을 기록해야 한다. 배열은 총 네 개가 필요하다.

1. 연산 횟수(거리): dist[]
2. 이전 연산 결과: pre[]
3. 명령어: cmd[]
4. 방문처리: visited[]

10000개의 정점 중 A에서 B로 연산하기 위한 명령어 개수를 예측할 수 없다. cmd[]에 모든 연산 과정을 저장할 경우 배열 크기가 한없이 커질 수 있어 이전 연산 과정을 cmd[i]에 모두 저장하는 것은 바람직하지 않다.

pre[]을 통해 이전 연산 결과를 역추적할 수 있으므로 cmd[]에는 i를 만들기 위한 가장 최근 명령어만 저장하자.

i	dist[]	pre[]	cmd[]
0	2	1	‘S’
1	1	2	‘S’
2	0	-1	-
3	2	4	‘S’
4	1	2	‘D’
5	3	0	‘S’

0~5까지의 수 범위 중 2에서 3으로 이동하기 위한 최소 연산을 생각해보자. 아래 번호는 이동 거리 dist의 값이 된다.

1. 이동 거리가 0인 수는 2만 해당한다. 이전 값은 없으므로 -1, 명령어는 빈 칸으로 초기화한다.

2. 2에서 2를 곱한 수(D) 4와 1을 감산한 수(S) 1이 해당한다.

3. 4에서 1을 감산한 수(S) 3과 1에서 1을 감산한 수 0이 각각 이동거리 2를 갖는다.

따라서 2에서 3을 계산하기 위한 연산 과정은 총 2번이 된다. pre 배열을 통해 명령어를 역추적한 문자열은 SD가 되며 최종 결과로 DS를 출력한다.

---

3. 소스 코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

int t, a, b, num, cal;
int dist[10001];
int pre[10001];
char cmd[10001];
bool visited[10001];
queue<int> q;

int main()
{
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d %d", &a, &b);
        
		// 각 text마다 배열 초기화
		memset(dist, 0, sizeof(dist));
		memset(pre, 0, sizeof(pre));
		memset(cmd, 0, sizeof(cmd));
		memset(visited, 0, sizeof(visited));

		dist[a] = 0;
		pre[a] = -1;
		visited[a] = true;
		q.push(a);

		while (!q.empty())
		{
			num = q.front();
			q.pop();
			
			// num*2
			cal = num * 2;
			if (cal > 9999) cal = cal % 10000;
			if (visited[cal] == 0)
			{
				q.push(cal);
				dist[cal] = dist[num] + 1;
				pre[cal] = num;
				cmd[cal] = 'D';
				visited[cal] = 1;
			}

			// num-1
			cal = num - 1;
			if (cal == -1) cal = 9999;
			if (visited[cal] == 0)
			{
				q.push(cal);
				dist[cal] = dist[num] + 1;
				pre[cal] = num;
				cmd[cal] = 'S';
				visited[cal] = 1;
			}
			
			// 왼쪽으로 num 자릿수 이동
			cal = (num % 1000) * 10 + num / 1000;
			if (visited[cal] == 0)
			{
				q.push(cal);
				dist[cal] = dist[num] + 1;
				pre[cal] = num;
				cmd[cal] = 'L';
				visited[cal] = 1;
				
			}
			
			// 오른쪽으로 num 자릿수 이동
			cal = (num / 10) + (num % 10) * 1000;
			if (visited[cal] == 0)
			{
				q.push(cal);
				dist[cal] = dist[num] + 1;
				pre[cal] = num;
				cmd[cal] = 'R';
				visited[cal] = 1;
			}
		}
		
		// 문자열 초기화 및 결과값 할당
		string result;
		while (b != a)
		{
			result.push_back(cmd[b]);
			b = pre[b];
		}
        
		// 문자열 역출력
		while (!result.empty())
		{
			printf("%c", result.back());
			result.pop_back();
		}
		printf("\n");
	}
}

---

4. 생각 정리

케이스마다 bfs를 나누어 해결하는 문제다. 조건에 맞는 bfs 알고리즘을 여러 번 작성해도 원하는 값에 도달할 수 있다. 무작정 알고리즘 코드를 외우려고 하지 말고 이론을 완벽히 이해하는 게 중요하다.

코드 작성 도중 바보 같은 실수를 했다. 케이스마다 연산 배열과 결과 문자열을 초기화해야 테스트를 여러 번 반복해도 프로그램이 동작할 수 있다… 는 사실을 잊어버리고 전역으로 배열과 문자열을 초기화한 것이다. 케이스를 여러 번 반복할 때 다시 쓰이는 변수가 없는지, 데이터 덮어쓰기가 허용되는지(a, b처럼!) 고려하면서 코드를 작성하는 게 좋겠다. 그리고 꼭 프로그램 동작 과정을 생각하면서 코드를 쓸 것!! 같은 실수를 반복하지 않도록 노력하자.