백준 16397 [C++]

www.acmicpc.net/problem/16397

16397번: 탈출

1. 풀이방법

 

- 처음에는 재귀를 이용한 DFS로 모든 경우를 탐색하려고 생각하고 코드를 구상했으나,

 

- 문제 조건을 보시면 T가 최대 99,999이고, A버튼만 누를 경우 숫자가 1씩 증가하는데 N이 0일경우를 생각해보면

 

- 재귀를 이용해서 짰을때 stackoverflow를 만났습니다. (조건을 보고 미리 생각했어야되는데....으휴 덤벙덤벙)

 

- 원리는 비슷한데 queue를 이용해서 bfs로 똑같이 옮겨서 해결했습니다.

 

 

 

2. 주의사항

 

- 조건도 꼼꼼히 파악하자.

 

 

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

int N, T, G;
bool visit[100000];
queue<pair<int,int>> tmpq;



int getmodnum(int tmp) {
	int maxmod = 1;
	while (1) {
		if (tmp == 0) break;
		tmp /= 10;
		maxmod *= 10;
	}
	maxmod /= 10;
	return maxmod;
}

int bfs() {
	while (!tmpq.empty()) {
		int tmpn = tmpq.front().first;
		int tmpcnt = tmpq.front().second;
		tmpq.pop();
		if (tmpcnt > T) break;
		if (tmpn == G) return tmpcnt;

		int num = tmpn + 1;
		if (num < 100000 && visit[num] == false) {
			visit[num] = true;
			tmpq.push({ num,tmpcnt + 1 });
		}

		num = tmpn * 2;
		if (num < 100000) {
			int minusnum = getmodnum(num);
			num -= minusnum;
			if (num < 100000 && visit[num] == false) {
				visit[num] = true;
				tmpq.push({ num,tmpcnt + 1 });
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> T >> G;
	tmpq.push({N, 0}); //시작점
	visit[N] = true;
	int result = bfs();
	if (result == -1) cout << "ANG" << "\n";
	else cout << result << "\n";
	return 0;
}