백준 16397번 탈출

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

16397번: 탈출

 

 

 

 

 

<접근방법>

완전탐색 문제입니다.

최단시간이므로 bfs가 좋을 거 같습니다.

 

다이어트를 조금 할 수 있을 거 같군요.

전에 만들어진 숫자에 대해서는 결과가 똑같기 때문에 굳이 볼 필요가 없습니다.

따라서 중복체크를 해줍니다.

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <time.h>
using namespace std;

struct info {
	int now, t;
};

int n, T, G;
bool cache[100000];

queue<info> q;

int bfs() {
	q.push({ n, 0});
	cache[n] = true;

	while (!q.empty()) {
		info t = q.front();
		q.pop();

		int now = t.now;
		int time = t.t;

		if (time > T) return -1;

		if (now == G) {
			return time;
		}

		//A
		int A = now + 1;
		if (A < 100000 && !cache[A]) {
			q.push({ A, time + 1 });
			cache[A] = true;
		}
		
		//B
		int B = now*2;
		if (B >= 100000) continue;

		//가장 큰 자릿수 구하기
		int div = 10000;
		while(1) {
			if (B == 0) break;
			if (B / div != 0) break;
			div /= 10;
		}
		B -= div;

		if (B >= 0 && !cache[B]) {
			q.push({ B, time + 1 });
			cache[B] = true;
		}
	}

	return -1;
}


int main() {
	cin >> n >> T >> G;

	int res = bfs();
	if (res == -1) {
		cout << "ANG" << '\n';
	}
	else {
		cout << res << '\n';
	}
	
	return 0;
}

 

 

---

 

 

<느낀 점>

- clock_t를 배웠다. 매우 유용하게 쓸 수 있을 거 같다