[C++] 백준 1697번 문제풀이

문제를 보고 든 생각은 내가 숫자를 X2 또는 +1 또는 -1 을 이용하여

K에 도달하도록 만드는 것이 였다.

그러나 문제를 풀수록 멍청한 생각이였단걸 알았고

BFS를 통해 쉽게 풀 수 있었다.

(내가 풀지 말고 컴퓨터를 이용하여 풀도록 하자)

BFS를 배워도 그것을 떠올리고 풀기가 쉽지 않았다....

문제를 보고 어떤식으로 풀어야겠다 이 단계에서 BFS DFS 트리 등등을 떠올릴 수 있어야 하는데

그 단계 까지 가진 못했다. 그 동안 배운 자료구조를 풀어서 정리 해봐야겠다...

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
bool visited[1000001];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int N, K;
	cin >> N >> K;
	queue<pair<int, int>>q;
	q.push(pair<int, int>(N, 0));
	while (!q.empty()) {
		int first = q.front().first;
		int second = q.front().second;
		if (first == K)
			break;
		q.pop();
		visited[first] = true;
		if (first + 1 <= 1000000 && !visited[first+1])
			q.push(pair<int, int>(first + 1, second + 1));
		if (first - 1 >= 0 && !visited[first - 1])
			q.push(pair<int, int>(first - 1, second + 1));
		if (first * 2 <= 100000 && !visited[first * 2])
			q.push(pair<int, int>(first * 2, second + 1));

	}
	cout << q.front().second << "\n";
}