C++ / 백준 / 16397 / 탈출

문제

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

16397번: 탈출

문제풀이

크게 어렵지는 않은 문제이다.

while(!q.empty())문에서 T 횟수를 넘기면 break를 해서 "ANG"을 출력하려고 했는데

45%쯤에서 실패가 떠서 반례가 있나 찾으러 다녔는데 반례는 없었고 break문을 거는 조건에서 실수를 해서 헤맸다.

 

같은 숫자는 확인 안 하도록 visit벡터를 이용한다.

숫자를 입력받고 숫자+1 값을 방문 안 했으면 q에 push,

숫자*2를 하고 idx를 10000부터 1까지 10으로 계속 나누면서 0이 아닌 맨 앞자리를 찾도록 한다.

숫자+1이든, 숫자*2 값이든 99999를 넘기면 안 되므로 조건에 넣는다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N(0), T(0), G(0);
	int idx(0);

	cin >> N >> T >> G;

	queue<pair<int, int>>q;
	vector<bool>visit(100000, false);

	q.push({ N,0 });
	visit[N] = true;

	while (!q.empty()) {
		int num = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (cnt > T)
			break;
		else if (num == G) {
			cout << cnt;
			return 0;
		}

		if (num + 1 <= 99999 && !visit[num + 1]) {
			q.push({ num + 1,cnt + 1 });
			visit[num + 1] = true;
		}

		num *= 2;
		if (num <= 99999) {
			for (idx = 10000; idx >= 1; idx /= 10) {
				if ((num / idx) != 0) {
					if (!visit[num - idx]) {
						q.push({ num - idx, cnt + 1 });
						visit[num - idx] = true;
					}
					break;
				}
			}
		}
	}
	cout << "ANG";
}