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

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

숨바꼭질 문제와 비슷한 BFS 문제

주의할 점은 이동의 순서를 순간이동 -> 뒤로 가기로 맞춰야 한다는 점입니다.

 

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 200001
using namespace std;

int n, k;
int visit[MAX];

void BFS() {
	memset(visit, -1, sizeof(visit));
	queue<int> q;
	q.push(n);
	visit[n] = 0;
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		if(now == k) {
			cout<<visit[k];
			break;
		}
        
        // 순간이동이 0초 소요되므로 먼저 순간이동을 최대한 진행한 후,
        // 동생의 위치를 맞추기 위해 중간중간 뒤로 이동하는 것이 가장 빠르게 동생에게 도착할 수 있다.
		if(now * 2 <= 100000 && visit[now * 2] == -1) {
			q.push(now * 2);
			visit[now * 2] = visit[now]; // 순간이동은 0초 소요
		}
        if(now -1 >= 0 && visit[now - 1] == -1) {
			q.push(now - 1);
			visit[now - 1] = visit[now] + 1;
		}
		if(now + 1 <= 100000 && 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;
	BFS();
}