[백준] c++ 13549번 숨바꼭질 3 (bfs풀이)

 

풀이)

이 전에도 이와 비슷한 문제를 bfs를 이용하여 풀었는데, 이번에도 마찬가지로 bfs를 이용하여 문제를 풀었습니다.

다른 풀이로는 다익스트라 알고리즘을 사용할 수 있습니다.

 

실수 중에 조심해야할 점은 탐색하는 다음 노드가 MAX 범위를 넘어가지 않도록 범위 설정을 해주는 것입니다.

백준에서 정답률이 낮은 문제는 보통, 숫자의 범위를 생각해야되는 경우가 많은 것 같습니다. 

 

 

코드)

 

#include<iostream>
#include<vector>
#include<queue>
#include<limits>
using namespace std;


int n, k;
const int MAX = 100'001;
const int INF = numeric_limits<int>::max();

vector<int> visited(MAX, INF);


void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = 0;

	while (not q.empty()) {
		int current = q.front();
		q.pop();

		int cnt = visited[current];
		
		int nx = current + 1;
		if (0 <= nx && nx < MAX && visited[nx] > cnt + 1){
			q.push(nx);
			visited[nx] = cnt + 1;
		}

		nx = current - 1;
		if (0 <= nx && nx < MAX && visited[nx] > cnt + 1) {
			q.push(nx);
			visited[nx] = cnt + 1;
		}


		nx = current * 2;
		if (0 <= nx && nx < MAX && visited[nx] > cnt ) {
			q.push(nx);
			visited[nx] = cnt;
		}

	}

}

int main()
{

	cin >> n >> k;
	bfs(n);

	cout << visited[k];

}