[c++/백준] 13549번: 숨바꼭질 3

문제 링크

13549번: 숨바꼭질 3

풀이

딱 봤을 때 BFS로 푸는 문제인건 알았는데 꽤 헤맸음 ...

1. arr에는 각 위치에 도달하는 최소 시간을 저장함
2. 먼저 arr를 무한대로 초기화 해주고, arr[n]을 0으로 둔다.(수빈 위치)
   queue인 pos에도 push 해줌
3. pos가 빌 때까지 계속하는데, 수빈의 위치(x)가 동생의 위치(k)가 된다면 return,
   3-1. 아니라면 x-1, x+1, x*2의 위치를 푸시해주는데, 이 때 수빈의 위치 범위가 유효하다면, 다음 위치의 도달 시간이 현재 위치 도달 시간보다 크다면 푸시해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
#define MAX 200000

using namespace std;

int n, k;
vector<int> arr;

int BFS()
{
	queue<int> pos;
	pos.push(n);
	arr[n] = 0;

	while (!pos.empty())
	{
		int x = pos.front();
		pos.pop();

		if (x == k) return arr[k];

		if (x*2 < MAX && arr[x * 2] > arr[x]) {
			arr[x * 2] = arr[x];
			pos.push(x*2);
		}

		if (x-1 >=0 && arr[x - 1] > arr[x]+1) {
			arr[x - 1] = arr[x]+1;
			pos.push(x-1);
		}

		if (x+1 < MAX && arr[x + 1] > arr[x]+1) {
			arr[x + 1] = arr[x]+1;
			pos.push(x+1);
		}
	}
}

int main()
{
	cin >> n >> k;
	arr.resize(MAX, MAX);

	cout<<BFS();
}