[BOJ 16397 // C++] 탈출

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16397번 문제인 탈출이다.
문제는 아래 링크를 확인하자.

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

16397번: 탈출

LED에 N이 떠있는 상태를 노드N으로, 버튼 A와 B를 눌러 LED에 떠있는 숫자를 x에서 y로 바꾸는 행위를 노드x에서 노드y로의 간선으로 대응시켜 주어진 문제를 방향그래프로 모델링할 수 있다. 위 그래프에서 노드S에서 노드G까지의 최단거리를 구하고, 그 값을 T와 비교해 문제를 해결하자.

 

ANG을 출력해야 하는 경우는 (1) S에서 G까지 도달할 수 없거나 (2) 도달할 수 있지만 그 거리가 T보다 큰 경우이다.

 

아래는 제출한 소스코드이다.

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

int N, T, G;
int dist[100000];

void bfs() {
	dist[N] = 1;
	queue<int> que;
	que.push(N);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		int nxt = cur + 1;
		if (nxt < 100000 && dist[nxt] == 0) {
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
		if (cur > 0) {
			nxt = cur * 2;
			if (nxt > 99999) continue;
			int e10 = 100000;
			while (e10 > nxt) e10 /= 10;
			nxt -= e10;
			if (dist[nxt] == 0) {
				dist[nxt] = dist[cur] + 1;
				que.push(nxt);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> T >> G;
	bfs();

	int ans = dist[G] - 1;
	if (0 <= ans && ans <= T) cout << ans;
	else cout << "ANG";
}