BOJ 1697 - 숨바꼭질

문제

https://www.acmicpc.net/problem/1697

풀이

수빈이가 좌표 N에서 동생이 있는 좌표 K를 찾아가야하는데 수빈이가 동생을 찾는 가장 빠른 시간, 즉 최소 비용을 찾는 문제다. 수빈이는 걷거나 순간 이동을 할 수 있는데 수빈이의 현재 좌표를 X라 할때 X+1, X-1, X*2로 이동할 수 있으며 모든 동작에는 1초의 시간이 걸린다고 한다. 최소 비용을 찾고, 모든 정점의 가중치가 1(초)로 똑같기 때문에 BFS로 해결 할 수 있다. 풀면서 아래의 조건을 체크하여 반복 횟수를 줄였다.

1. (당연하지만) 한번 방문한 정점은 다시 안가도 된다. 
2. 최소 비용이 될 수 있는 후보 중 가장 작은 값보다 현재 비용이 크다면 바로 답이 아니라 간주한다.

#include <cstdio>
#include <queue>
using namespace std;
struct movement{
	int x,step;
};
queue<movement> q;
int visit[100001] = {0};
int abs(int x) {return x>0?x:-x;}
int main(){
	int n,k,i,ans;
	movement move;
	
	scanf("%d%d",&n,&k);
	move.x = n;
	move.step = 0;
	
	ans=abs(n-k);

	if(n >= k){
		printf("%d",ans);
		return 0;
	}

	q.push(move);
	while(!q.empty()){
		q.front();
		
		if(q.front().step >= ans){
			q.pop();
			continue;
		}

		if(q.front().x == k) {
			ans = q.front().step;
			q.pop();
			continue;
		}

		move.step = q.front().step + 1;

		if(q.front().x*2 <= 100000 && q.front().x*2 >= 0 && !visit[q.front().x*2]){
			move.x = q.front().x * 2;
			visit[move.x] = 1;
			q.push(move);
		}

		if(q.front().x +1 <= 100000 && !visit[q.front().x+1]) {
			move.x = q.front().x + 1;
			visit[move.x] = 1;
			q.push(move);
		}
		if(q.front().x - 1 >= 0 && !visit[q.front().x-1]){
			move.x = q.front().x - 1;	
			visit[move.x] = 1;
			q.push(move);
		}
		q.pop();
	}
	printf("%d",ans);
}