[백준/C++] 16953번 A → B

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

16953번: A → B

 

#include <bits/stdc++.h>
using namespace std;

template <typename T>
void prt(const vector <T>& v1) {
	cout << endl;
	for (int i = 0; i < v1.size(); i++) {
		for (int j = 0; j < v1[i].size(); j++) {
			cout << v1[i][j] << " ";
		}
		cout << endl;
	}
}
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int start, end; cin >> start >> end;
	/*bool* visit = new bool[end + 1];
	fill(visit, visit + end + 1, 0);*/

	int cnt = 0;

	queue <pair<long long, long long>> q;
	pair <long long, long long> tmp;
	q.push({ start, 0 });
	
    // 도달할 수 없을 경우를 위한 flag 생성
	bool flag = false;

	while (!q.empty()) {
		tmp = q.front(); q.pop();
		long long now = tmp.first;
		if (now == end) {
			cout << tmp.second+1;
            // 도달한다면 flag를 true로 바꿔줌
			flag = true;
			break;
		}
        
		long long next1 = now * 2;
		long long next2 = now * 10 + 1;

		// 범위가 넘어가지 않는 선에서 queue에 삽입해준다.
		if (next1 <= end)
			q.push({ next1, tmp.second + 1 });
		if (next2 <= end)
			q.push({ next2, tmp.second + 1 });
	}

	if (flag == false)
		cout << "-1";

}

 

 

주의할 점

1. 자료형 범위 체크 int -> long long (오버플로우)

2. visit 배열은 필요 없음 -> 메모리 초과