개요

백준 16397: 탈출

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

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

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

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

접근방식

1. 백준 1697 :숨바꼭질 문제처럼 함수포인터를 이용해 함수 배열을 만든 뒤,
   A버튼 B버튼 구현을 하였다.

   //람다함수와 function을 사용한 함수 포인터
   const function<int(int n)> f[2] = {
   
   	//a버튼
   	[](int n) {return n + 1; },
      
      	//b버튼 
   	[](int n) {
   		//n이 0이라면 b버튼 눌러도 0임(조건) 
   		if (n == 0) return 0;
   		//2를 곱한값 변수에 할당
   		int inputNum = 2 * n;
   		//99만 9999넘어가면 -1 return
   		if (inputNum > 99'999) return -1;
   		//안넘어가면 2*n의 자릿수 구한후 제일 높은자리수 -1해준 후 return
   		else {
   			int cnt = 1;
   			while (inputNum/10 !=  0) {
   				cnt *= 10;
   				inputNum /= 10;
   			}
   			return 2 * n - cnt;
   		}
   	}
   
   };
   

   b버튼에서 높은 자리수 구하는 방법은 10으로 나눌 수 있다면
   변수 cnt에 10을 계속 곱해줘서 cnt를 inputNum과 자릿수를 맞춰준 후
   빼줬다.
   

2. 숨바꼭질 문제와 차이점은 버튼을 누를 최대 횟수를 문제로 준다는 것이였다.
   따라서 maxButtonPress값을 받아온 후,
   매번 bfs함수를 실행할때마다 1씩 줄여주고 버튼을 누른 후, 0이하로 내려가면
   목적 숫자에 도달을 못한다는 뜻 이므로 ang출력해줬다.

3. 시작지점과 출력지점이 같을 경우, 빙돌아서 도달하게 되므로
   solution함수 맨 처음에 if 처리로 0출력하도록 구현하였다.

코드

#include<iostream>
#include<functional>
#include<queue>

using namespace std;
queue<int> q;
int number=0, maxButtonPress = 0, Goal = 0;
bool visited[100'001];

//function을 사용한 함수 포인터
const function<int(int n)> f[2] = {
	//a버튼
	[](int n) {return n + 1; },
	//b버튼 
	[](int n) {
		//n이 0이라면 b버튼 눌러도 0임(조건) 
		if (n == 0) return 0;
		//2를 곱한값 변수에 할당
		int inputNum = 2 * n;
		//99만 9999넘어가면 -1 return
		if (inputNum > 99'999) return -1;
		//안넘어가면 2*n의 자릿수 구한후 제일 높은자리수 -1해준 후 return
		else {
			int cnt = 1;
			while (inputNum/10 !=  0) {
				cnt *= 10;
				inputNum /= 10;
			}
			return 2 * n - cnt;
		}
	}

};

void input() {
	cin >>number>> maxButtonPress >> Goal;
	q.push(number);
	visited[number] = true;
}


void solution() {
	//만약 목적지와 시작숫자가 같으면 누를이유가 없으므로 0 출력해버리기
	if (Goal == number) {
		cout << 0;
		return;
	}

	int level = 1;
	//bfs에서 큐가 빌때까지 반복, level증가
	for (; !q.empty(); level++) {
		//큐는 가변적이므로 사이즈 미리 할당
		int qSize = q.size();
		//각 레벨 당 버튼한번 누르는 경우이므로 레벨 진행하기전에 하나 감소
		maxButtonPress--;
		// 각 레벨의 노드수만큼 반복문 진행
		for (int i = 0; i < qSize; i++) {
			int cur = q.front();
			q.pop();
			for (int i = 0; i < 2; i++) {
				int nextN = f[i](cur);
				if (nextN == Goal) {
					cout << level;
					return;
				}
				//범위 벗어나면 continue
				if (nextN < 0 || nextN>99'999) continue;
				//이미 방문한 수면 continue
				if (visited[nextN]) continue;
				//방문 처리
				visited[nextN] = true;
				//큐에 넣어주기
				q.push(nextN);
			}
		}
		//버튼을 누른 경우의 수가 다끝났을때 0이하면 더이상 못누르므로 ang출력
		if (maxButtonPress <= 0) {
			cout << "ANG";
			return;
		}
	}
	//반복문끝나면 ang출력
	cout << "ANG";
}

int main() {
	input();
	solution();
}

문풀후생

1. b버튼에서 10으로 나눴을 때 몫이 0이 아닌 부분을 판별하는 과정에서
   inputNum/=10 이부분을 빼먹어서 무한 루프가 걸렸다.
   람다식에서 무한루프가 돌줄은 생각도 못해서 solution부분 계속 검토하고 디버깅하다가 찾았다..

2. maxButtonPress가 음수일때 ang출력했다가 답이 안 나왔다.
   단순히 1이라 두고 생각해도 한번 누르면 0이되서 못눌러야하는데
   음수로 if문을 만드니 두번 누를수 있었다..

3. 제일 시간 많이 들었던 부분은 최대 버튼횟수 채운 관계로 목적숫자에 못 도달하면 ANG가 아니라 Ang이라고 출력해서 오답이 계속 나왔다.
   이것도 모르고 반례찾겠다고 시간을 너무 낭비했다,,
   출력부분도 신경쓰자..