백준 16397: 탈출

문제 요약

벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.

버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.

1. 버튼 A를 누르면 N이 1 증가한다.
2. 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 예를 들어 123→146으로, 5→0으로, 3→5로 변한다. 단, N이 0이면 버튼 B를 눌러도 수가 변하지 않는다.
3. LED가 다섯 자리까지밖에 없기 때문에 N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
4. 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.

최대 T회 버튼을 누를 수 있고, 그 횟수 안에 LED로 표현된 N을 G와 같게 만들어야 탈출할 수 있다는 사실을 알아냈다.

홍익이의 방 탈출을 기원하며, 탈출에 필요한 최소의 버튼 횟수를 구하자.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 된다. 단, 겉 while문의 조건이 큐가 빌 때까지가 아닌, 자기 자신도 포함하여 t + 1번 반복하면 된다.

n + 1은 g보다 작은 경우에만 큐에 퓨쉬하고, n * 2쪽은 n * 2가 100,000미만이며, n의 자리수를 while문으로 구해서 10의 거듭제곱으로 빼면 된다.

예를 들어 먼저 n에 n * 2를 대입하여 그 n이 892일 경우, n / dec가 0이 되는 dec를 구한 후, (여기서는 1000)그 dec를 10으로 나누어 빼면 된다. (892 - 1000/10 = 792)

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<int> q;
bool visited[100000];

int main()
{
	int n, t, g, level = -1, qsize, dec;
	bool sol = false;
	cin >> n >> t >> g;

	visited[n] = true;
	q.push(n);
	t++;
	while (t--) {
		level++;
		qsize = q.size();
		while (qsize--) {
			n = q.front();
			q.pop();
			dec = 10;
			if (n == g) {
				sol = true;
				break;
			}
			if (n + 1 <= g) {
				if (!visited[n + 1]) {
					visited[n + 1] = true;
					q.push(n + 1);
				}
			}
			n *= 2;
			if (n < 100000) {
				while (n / dec != 0) dec *= 10;
				dec /= 10;
				n -= dec;
				if (n < 0) n = 0;
				if (!visited[n]) {
					visited[n] = true;
					q.push(n);
				}
			}

		}
		if (sol) break;
	}
	if (sol) printf("%d", level);
	else printf("ANG");
	
	return 0;
}