숨바꼭질 C++ - 백준 1679

https://acmicpc.net/problem/1697

이 문제는 bfs 문제이다.

bfs로 가장 먼저 도달한 지점이 항상 최소 시간이므로
도달한 지점에 또 도달하지 않게 작성해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MAX 100000+1
using namespace std;

int n;
int k;
int graph[MAX];
int t[MAX];
bool flag=false;

void bfs(){
	queue<int> q;
	q.push(n);
	while(!q.empty() && !flag){
		int x=q.front();q.pop();
		for(int nx:{x-1,x+1,2*x}){
			if(nx==k){
				cout << t[x]+1;
				flag=true;
				break;
			}
			if(100000<nx || nx<0) continue;
			if(t[nx]!=-1) continue;
			t[nx]=t[x]+1;
			q.push(nx);
		}
	}
}

int main(){
	cin >> n >> k;
	memset(t,-1,sizeof(t));
	t[n]=0;
	if(n>=k){
		cout << n-k;
	}
	else{
		bfs();
	}
}