백준 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와 같게 만들어야 탈출할 수 있다는 사실을 알아냈다.

똑똑한 홍익이는 이와중에 자존심이 발동해 버튼 누르는 횟수를 최소로 하여 방을 탈출하기로 했다.

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

입력

첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다.

각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다.

출력

첫 번째 줄에 탈출에 필요한 최소의 버튼 횟수를 출력한다.

만약 탈출할 수 없다면 “ANG”을 따옴표 없이 출력한다.

 

 

 

 

 

 

아직 DFS와 BFS를 많이 다뤄보지 못해서 구현이 서투른 것 같다.

이 문제는 BFS 문제인데 이유는 목적 숫자에 도달하는데에 있어서 버튼을 누르는 순서의 경우의 수가 존재한다.

 

카운트 1번째에 A버튼을 누르는지 B버튼을 누르는지에 따라 파생되는 경우의 수가 갈리고 

각각의 카운트에 어떤 버튼을 누르는지에 대해 일련의 순서가 존재한다.

결국 어떤 경로를 쫒아 갔을 때 목적 숫자에 도달하지 못하면 버려져야 하고 다음 루트로 복귀해야 한다.

따라서 탐색 방법으로 DFS 혹은 BFS를 사용해야 하는데 queue를 사용해서 BFS를 구현해 보았다.

queue에 각 데이터를 입력시킨다. 첫번째 버튼에 대해 입력이 들어온 후 

그 데이터를 뽑으면서 pop시킨다. 그리고 queue에는 현재 뽑아진 데이터에 대해  새로운 루트가 생긴다.

현재 데이터 기준으로 A, B인 경우에 대해 각 데이터를 같은 카운트 값으로 push시킨다.

같은 카운트 값에 대해 다른 데이터 값이 queue에 순서대로 저장되있다.

데이터를 뽑고 pop시키고 그 데이터에 대해 새로운 경로를 추가하고 다시 pop시키고 

 

1 7 10 의 경우에는

0                                 1
1                                   2
2                                     3
3                                   5       4
4                                  0 6    7   5
5                                          8 
6                                           9
7                                            10

 

 

큐 저장 순서 1 2 3 5 4 0 6 7 5 8 9 10

탐색 순서     ->

만약 스택이 였다면 

1 2 3 5 4 7 5 8 9 10 조금 이상한  DFS가 되었을 것이지만

큐 이기 때문에 앞에서 부터 접근한다 BFS가 된다.

 

큐에 저장된 현재 값이 목표 값에 도달 했을 때를 비교 하려면 그 값까지도 큐에 저장이 되어야 뽑아 낼 수 있으므로 

주의 해야함.

 

탐색에 있어서는 방문기록이 필수 !

 

 

 

 

 

 

 

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;


int N,T,G;
bool V[100000];


int A(int X)
{
int F;
F=X+1;
return F;
}

int B(int X)
{

int F= 2*X;
int *arr = new int[5];

for(int i=4; i>=0; i--)
{

arr[i]=F%10;
F=F/10;


}

F=2*X;

for(int i=0; i<5; i++)
{
if(arr[i]!=0)
{
F=F-pow(10,4-i);
break;
}


}

return F;


}


int main(void)
{

int test;
cin>>N>>T>>G;

V[N]=true;

if(N>99999 || G<N)
{
cout<<"ANG";
}
else
{
queue  q;
queue  cnt;
q.push(N);
cnt.push(0);
V[N]=true;
while(!q.empty()&&!cnt.empty())
{   
int number =q.front();
int count = cnt.front();

q.pop();
cnt.pop();
    
if(number == G)
{
cout<<count;
return 0;
}

if(count>T){
cout<<"ANG";
return 0;
}

if(!V[B(number)] && B(number)<=G)
{

q.push(B(number));

cnt.push(count+1);
V[B(number)]=true;
}
if(!V[A(number)] && A(number)<=G)
{
q.push(A(number));
cnt.push(count+1);
V[A(number)]=true;


}



}
cout<<"ANG";



}




}