백준 13549 (숨바꼭질 3)

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

13549번: 숨바꼭질 3

해당 문제는 수빈이의 위치와 동생의 위치가 주어질 때 수빈이가 동생을 찾을 수 있는 가장 빠른 경우의 시간을 찾는 문제이다. 이때 수빈이의 이동할 수 있는 경우는 다음과 같다.

1. 수빈이는 1초 뒤에 +1, -1 번의 위치로 이동할 수 있다
2. 수빈이는 0초 뒤에 현재위치 * 2 의 위치로 이동할 수 있다.

위의 조건대로 움직인 좌표를 Queue 에넣고 BFS를 사용하는 방법으로 해결하면 된다. 추가적으로 현재 위치 * 2 의 경우에는 이동 시간이 0초 이므로 가장 먼저 연산을 수행하여 Queue에 Push 하도록 하여 가중치를 최대한 낮추도록 수행한다.

풀이 :

#include <iostream>
#include <queue>

using namespace std;

struct Node{
	int x;
	int cnt;
};
int target;
int now;
int map[100001];
int check[3] = { 2, -1, 1 };

int bfs(){
	queue<Node> qu;
	map[now] = 1;
	qu.push({ now, 0 });

	while (!qu.empty()){
		Node now = qu.front();
		if (now.x == target) return now.cnt;
		for (int i = 0; i < 3; ++i){
			int dx = now.x + check[i];
			if (i == 0) dx = now.x * check[i];
			if (dx < 0 || dx >= 100001) continue;
			if (map[dx] == 1) continue;
			map[dx] = 1;
			if (i == 0){
				qu.push({ dx, now.cnt });
			}
			else{
				qu.push({ dx, now.cnt + 1 });
			}
		}
		qu.pop();
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> now >> target;

	int res = bfs();
	cout << res << endl;

}