백준 16397 - 탈출(C++)

문제 링크입니다! https://www.acmicpc.net/problem/16397

16397번: 탈출

간단한 BFS 문제였습니다. 

문제 조건

출력 예시

N -> G까지 A or B 연산을 통해서 최소 몇번을 통해서 갈 수 있는지를 물어보는 문제입니다.

99999보다 작다는 조건만 해주면 쉽게 풀 수 있는 문제였습니다.

 

문제 접근 방법

1. N에서 시작해 A, B 연산을 했을 때의 값을 찾는다.

2. 값들이 99999보다 작을 때, 이전에 방문하지 않았다면, 방문했다고 표시한 뒤, BFS 탐색을 한다.

3. G에 도달했을 경우, t를 return 한다.

4. T보다 많이 이동했을 경우, -1을 return 한다.

 

 

문제 접근 방법 - 1~4번(bfs() 와 find_high(int x) 함수를 참고해주세요)

A연산의 경우 X에서 1를 더합니다.

B연산의 경우 X에 2를 곱한 뒤, 가장 큰 자릿수에서 1를 뺍니다.

A, B연산을 했을 경우 모두 99999보다는 작아야합니다. 

find_high(int x) 함수는 가장 큰 자릿수를 찾는 함수입니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, T, G;
int check[100000];
//A -> N+1, B -> N*2 + -1(가장 높은 자리)

int find_high(int x) {
	int ans = 1;
	while (1) {
		if (x == 0) break;
		ans *= 10;
		x /= 10;
	}
	return ans/10;
}

int bfs(int start) {
	queue<pair<int,int>> q;
	q.push(make_pair(start,0));
	check[start] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int t = q.front().second;
		q.pop();
		if (t > T) break;
		if (x == G) return t;
		int x1 = x + 1;
		int x2 = x * 2;
		if (x1 <= 99999) {
			if (check[x1] == 0) {
				check[x1] = 1;
				q.push(make_pair(x1, t+1));
			}
		}
		if (x2 <= 99999) {
			int num = find_high(x2);
			x2 -= num;
			if (check[x2] == 0) {
				check[x2] = 1;
				q.push(make_pair(x2, t + 1));
			}
		}
	}
	return -1;
}

void solve() {
	int ans = bfs(N);
	if (ans == -1) cout << "ANG";
	else cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> T >> G;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!