[백준/C++] 16397 탈출

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

코드

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

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
#define MAX 99999
int n, t, g, tmp;
bool visit[MAX];
string s;
queue<pair<int, int>> q;

void bfs() {
	while (!q.empty()) {
		int now = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (cnt > t) continue;

		if (now == g) {
			cout << cnt;
			return;
		}
		
		if (now + 1 <= MAX && !visit[now+1]) {
			q.push({ now + 1, cnt+1 });
			visit[now + 1] = true;
		}

		if (now * 2 <= MAX && now != 0) {
			s = to_string(now*2);
			s[0] -= 1;
			tmp = stoi(s);
			if (!visit[tmp]) {
				q.push({ tmp , cnt+1});
				visit[tmp] = true;
			}
		}
	}
	cout << "ANG";
}

int main() {
	FASTIO;
	cin >> n >> t >> g;
	q.push({ n, 0 });
	visit[n] = true;
	bfs();
	return 0;
}

설명

A를 누르면 N + 1이 되고 B를 누르면 N*2에서 0이 아닌 가장 높은 자릿수가 1이 줄어드는 것을 구현합니다. 큐에는 현재값과 버튼을 누른 횟수를 저장하고 BFS를 돌려줍니다. 

느낀 점

버튼의 동작 방식을 그대로 구현하고, 큐에는 {현재 값,  버튼 누른 횟수}를 기록해주면서 문제를 풀면 됩니다!