[백준] C++ 1697번 숨바꼭질 실버1 - 그래프

문제 : https://www.acmicpc.net/problem/1697
분류 : 그래프, 너비 우선 탐색(BFS)

접근

1. 3가지 상황에서 가장 빠른 시간을 위해야한다.
2. 그러려면 모든 경우의 수를 고려해야한다. 문제의 예를 보자.
   
   52(10)->10-1(9)->92(18)->18-1(17) 총 4번의 이동이 가장 빠른 시간이다.
3. 모든 경우를 확인해야 하기 때문에 너비 우선 탐색(BFS)를 활용한다.
4. 0 <= N, K <= 100000을 고려한다.

슈도코드

n q에 삽입

q가 빌 때까지
if n == k 끝
if n-1 
if n+1
if n*2
-> 방문처리, q에 삽입, n 변경,1텀 끝날 때마다 cnt++

풀이

#include<iostream>
#include<algorithm>
#include<queue>
#define MAX 100001
using namespace std;

void BFS(int N, int K) {
	queue<pair<int, int>> q;
	bool visited[MAX] = {false, };

	q.push(make_pair(N, 0));
	visited[N] = true;
	
	while(!q.empty()) {
		int cur_N = q.front().first;
		int dist = q.front().second;
		q.pop();
		
		if (cur_N == K) {
			cout << dist;
			break;
		}
		
		if (cur_N - 1 >= 0 && !visited[cur_N - 1]) {
			visited[cur_N - 1] = true;
			q.push({cur_N - 1, dist + 1});
		}
		if (cur_N + 1 < MAX && !visited[cur_N + 1]) {
			visited[cur_N + 1] = true;
			q.push({cur_N + 1, dist + 1});
		}
		if (cur_N * 2 < MAX && !visited[cur_N * 2]) {
			visited[cur_N * 2] = true;
			q.push({cur_N * 2, dist + 1});
		}
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	int N, K;
	cin >> N >> K;
	BFS(N, K);
	return 0;	
}