[G4] 백준 16397번 탈출 C++ 너비 우선 탐색

리뷰

 

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

골드 4보단 실버 1정도가 어울리는 문제인 것 같다.

 

 

전역 변수

• n : 십진수의 초기값을 저장할 변수
• t : 버튼을 누를 수 있는 최대 수를 저장할 변수
• g : 십진수의 목표값을 저장할 변수
• v : 방문 정보를 저장할 배열
• Cur : 현재 숫자와 누적 버튼 클릭 횟수를 정의할 구조체

 

함수

1. bfs

int bfs() {
	queue<Cur> q;
	q.push({ n, 0 });
	v[n] = true;

	while (!q.empty()) {
		Cur cur = q.front(); q.pop();
		int p = cur.x, ct = cur.y;

		if (ct > t) continue;
		if (p == g) return ct;
		//cout << p << " " << v[p] << "\n";
		
		if (p + 1 < 1e5 && !v[p + 1]) {
			v[p + 1] = true;
			q.push({ p + 1, ct + 1 });
		}

		if (p * 2 >= 1e5) continue;
		string b = to_string(p * 2);
		if (b[0] > '0') b[0]--;
		int B = stoi(b);
		if (B < 1e5 && !v[B]) {
			v[B] = true;
			q.push({ B, ct + 1 });
		}
	}
	return -1;
}

 

초기 값에서 목표 값까지 도달하기 까지 걸린 최소 버튼 클릭 횟수를 구하는 함수

 

 

문제풀이

1. n, t, p값을 입력 받고, bfs함수를 호출한다.
2. Cur타입의 큐 q를 초기화 하고, 초깃값 n과 누적 버튼 클릭 횟수 0을 push해준다.
3. 초깃값 n을 방문처리 하고 q가 빌때까지 while루프를 수행한다.
4. 변수 p와 ct에 현재 값과 누적 버튼 클릭 횟수를 파싱해 준다.
5. 기저 조건으로 ct가 t보다 클 경우 continue, p가 g과 같을 경우 ct를 리턴해 준다.
6. p + 1이 10만보다 작고 방문하지 않았으면 방문처리 후 클릭 수를 늘려 q에 삽입해 준다.
7. p * 2가 10만보다 작고 p * 2의 첫번째 자릿수를 줄인 값이 방문처리 되지 않았으면 q에 삽입해 준다.
8. while루프가 종료될 때 까지 기저조건에 도달하지 못했다면 -1을 리턴해 준다.
9. bfs함수의 리턴값을 res에 저장해 주고, -1이 아니라면 그대로, 아니라면 "ANG"을 출력해 준다.

 

트러블 슈팅

없

 

 

참고 사항

• 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 예를 들어 123→146으로, 5→0으로, 3→5로 변한다. 단, N이 0이면 버튼 B를 눌러도 수가 변하지 않는다.
• LED가 다섯 자리까지밖에 없기 때문에 N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
• 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.

 

정답 코드

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

int n, t, g;
bool v[100000];
struct Cur {
	int x, y;
};

int bfs() {
	queue<Cur> q;
	q.push({ n, 0 });
	v[n] = true;

	while (!q.empty()) {
		Cur cur = q.front(); q.pop();
		int p = cur.x, ct = cur.y;

		if (ct > t) continue;
		if (p == g) return ct;
		//cout << p << " " << v[p] << "\n";
		
		if (p + 1 < 1e5 && !v[p + 1]) {
			v[p + 1] = true;
			q.push({ p + 1, ct + 1 });
		}

		if (p * 2 >= 1e5) continue;
		string b = to_string(p * 2);
		if (b[0] > '0') b[0]--;
		int B = stoi(b);
		if (B < 1e5 && !v[B]) {
			v[B] = true;
			q.push({ B, ct + 1 });
		}
	}
	return -1;
}

int main() {
	cin >> n >> t >> g;
	int res = bfs();
	if (res != -1) cout << res;
	else cout << "ANG";
}