[백준] 16397번 탈출 (C++, JAVA)

16397번: 탈출

버튼 A를 누르는 경우에는 큐의 front에 +1한 값으로 비교해주고

버튼 B를 누르는 경우에는 큐의 front에 *2한 값을 조건에 맞게 변형한 뒤 비교해준다.

 

나는 그 조건에 맞게 변형하기 위해 이걸 string 형태로 바꾸어

0인 경우는 그냥 0으로 놔두고

나머지 경우는 맨 앞자리 수를 1 낮춰주고

stoi 함수를 이용해 int로 바꾸었다.

그렇게 하면 맨 앞자리 수가 0일 땐 생략되어 자동으로 자릿수가 줄어든다.

(string 0123 -> int 123)

 

이렇게 큐가 empty할 때까지 돌렸는데도 G에 도달하지 못하거나

T회를 넘을 경우엔 실패이므로 ANG을 출력하고

G에 도달한 경우에는 그때까지 저장해두었던 횟수를 출력하면 된다.

 

< C++ 코드 >

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
queue <int> q, tmp;
int led[100000] = { 0 };
bool visited[100000] = { false };
int x, X, success = -1;
string y;
void Bfs(int N, int G, int T) {
	while (!q.empty()) {
		if (led[q.front()] > T) break;
		if (q.front() == G) {
			success = led[q.front()];
			break;
		}
		x = q.front() + 1; //버튼 A
		if (x < 100000 && visited[x] == false) {
			visited[x] = true;
			led[x] = led[q.front()] + 1;
			q.push(x);
		}
		x = q.front() * 2; //버튼 B
		y = to_string(x);
		if (y[0] != '0') y[0] -= 1;
		X = stoi(y);
		if (x < 100000 && visited[X] == false) {
			visited[X] = true;
			led[X] = led[q.front()] + 1;
			q.push(X);
		}
		q.pop();
	}
}

int main() {
	int N, T, G;
	cin >> N >> T >> G;
	visited[N] = true;
	q.push(N);
	Bfs(N, G, T);
	if (success == -1) cout << "ANG";
	else cout << success;
	return 0;
}

 

< JAVA 코드 >

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_16397_탈출 {
	private static int N, T, G;

	public static int bfs() {
		boolean chk[] = new boolean[100000];
		Queue <int[]> q = new LinkedList<>();
		q.offer(new int[] {N, 0});
		chk[N] = true;
		
		while(!q.isEmpty()) {
			int num[] = q.poll();
			
			if(num[1] > T) return -1;
			if(num[0] == G) return num[1];
			
			int tmp = num[0] + 1; // A 버튼
			if(tmp < 100000 && !chk[tmp]) {
				chk[tmp] = true;
				q.offer(new int[] {tmp, num[1] + 1});
			}
			
			tmp = num[0] * 2; // B 버튼
			if(tmp > 99999) continue; // 99999 넘으면 스킵
			String st = Integer.toString(tmp);
			tmp -= (int)Math.pow(10, st.length() - 1);
			if(tmp >= 0 && tmp < 100000 && !chk[tmp]) {
				chk[tmp] = true;
				q.offer(new int[] {tmp, num[1] + 1});
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); T = sc.nextInt(); G = sc.nextInt();
		
		int res = bfs();
		if(res == -1) System.out.println("ANG");
		else System.out.println(res);
	}
}