boj, 백준) 16397. 탈출 (C / C++)

1. 문제 링크

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

16397번: 탈출

2. 문제 개요

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를 넘지 않는다고 해도 탈출에 실패하게 된다.

 

위와 같은 조건이 있을 때, 버튼을 최소로 눌러서 N을 G와 같게 만들어라.

3. 문제 힌트

발생가능한 모든 경우의 수를 확인하는 전수조사 문제인데 최소 횟수로 방문하는 것이기 때문에 BFS를 사용할 수 있다.

 

BFS로 숫자를 탐색했을 때, 한번 거처간 곳을 한번 더 도착하게 된다면 최소가 아니기 때문에 더 탐색할 필요가 없다.

 

4. 문제 풀이

가장 처음 N을 Queue에 삽입하고 1개는 A, 1개는 B 버튼을 눌렀다 가정하고 Queue에 다시 삽입해줍시다.

 

3, 4번의 조건을 잘 생각해서 Queue에 삽입해 주어야 합니다.

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

bool visited[100000];
int n, t, g;

queue<pair<int, int>> q;

int Decrease(int b)
{
	vector<int> v;
	int ret = 0;

	while (b != 0)
	{
		v.push_back(b % 10);
		b /= 10;
	}
	
	if (v.size() > 0) {
		--v[v.size() - 1];

		for (int i = v.size() - 1; i >= 0; --i)
		{
			ret *= 10;
			ret += v[i];
		}
	}

	return ret;
}

int main()
{
	scanf("%d %d %d", &n, &t, &g);

	q.push({ n,0 });
	visited[n] = true;

	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();
		if (cur.second > t)
		{
			break;
		}
		if (cur.first == g)
		{
			printf("%d", cur.second);
			return 0;
		}
		//a
		int a = cur.first + 1;

		if (a <= 99999){
			if (!visited[a]){
				visited[a] = true;
				q.push({ a, cur.second + 1 });
			}
		}
		
		//b
		int b = cur.first * 2;
		if (b <= 99999)
		{
			b = Decrease(b);
			if (!visited[b]) {
				visited[b] = true;
				q.push({ b, cur.second + 1 });
			}
		}
	}

	printf("ANG");

	return 0;
}

6. 결과