[백준/BOJ] 1697번 숨바꼭질 (C++)

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

BFS 기초 문제

처음 수빈이의 위치에서 뒤로가는 경우, 앞으로 가는 경우, 순간이동 하는 경우를 계속 큐에 넣어가며 동생의 위치와 같아지는 순간을 구하여 그 시간을 출력한 후 종료

 

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

int n, k;
int visit[100001];

void BFS() {
	queue<int> q;
	q.push(n);
	visit[n] = 0;
	
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		
		if(now == k) {
			cout << visit[k]; 
			return;
		}
		
		if(now * 2 <= 100000 && visit[now * 2] == -1) {
			q.push(now * 2);
			visit[now * 2] = visit[now] + 1;
		}
		
		if(now + 1 <= 100001 && visit[now + 1] == -1) {
			q.push(now + 1);
			visit[now + 1] = visit[now] + 1;
		}
		
		if(now - 1 >= 0 && visit[now - 1] == -1) {
			q.push(now - 1);
			visit[now - 1] = visit[now] + 1;
		}
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
	cin >> n >> k;
	
	memset(visit, -1, sizeof(visit));
	BFS();
}