백준 / 13549 숨바꼭질 3 C++

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

수빈이와 동생의 위치가 주어져있을 때 수빈이가 최소 몇 번만에 동생한테 갈 수 있는지 구하는 문제입니다.

 

수빈이가 이동하는 경로는 현재 위치 +1 , -1, *2 인데, *2로 이동하는 경우는 0초, 나머지는 1초가 걸립니다.

현재 위치가 N일 때, 이동 가능한 위치는 N+1, N-1, N*2 3가지 이므로 3가지 위치에 대해 bfs를 진행하면 됩니다. 

주의할 점은 이미 이동했다하더라도, 새로운 경로로 더 나은 결과를 얻을 수 있으므로 이 또한 queue에 넣어야 합니다.

 

예를 들어, 아래와 같은 경우입니다.

현재 위치 1, 동생 위치 2

=> 1+1=2 => 1초 걸림, 2는 방문

=> 1*2=2 => 0초 걸림

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

#define MAX 100000
int n, k;
int dp[100001]; 
bool check[100001];

// 초기화
void init()
{
	cin >> n >> k;
	memset(dp, 987654321, sizeof(dp));
	memset(check, false, sizeof(check));
}

// 방문한적 없으면 dp[new] = dp[now] or dp[now]+1
// 방문한적 있는데 새로운 결과가 더 작은 값이면
// 그 값으로 업데이트 후 queue에 넣기
void bfs()
{
	queue<int>q;
	q.push(n);
	check[n] = true;
	dp[n] = 0;

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		if ((now + 1 >= 0) && (now + 1 <= MAX)) {
			if (check[now + 1] == false) {
				q.push(now + 1);
				check[now + 1] = true;
				dp[now + 1] = dp[now] + 1;
			}
			else {
				if (dp[now + 1] > dp[now] + 1) {
					q.push(now + 1);
					dp[now + 1] = dp[now] + 1;
				}
			}
		}

		if ((now - 1 >= 0) && (now - 1 <= MAX)) {
			if (check[now - 1] == false) {
				q.push(now - 1);
				check[now - 1] = true;
				dp[now - 1] = dp[now] + 1;
			}
			else {
				if (dp[now - 1] > dp[now] + 1) {
					q.push(now - 1);
					dp[now - 1] = dp[now] + 1;
				}
			}
		}

		if ((2 * now >= 0) && (2 * now <= MAX)) {
			if (check[2 * now] == false) {
				q.push(2 * now);
				check[2 * now] = true;
				dp[2 * now] = dp[now];
			}
			else {
				if (dp[2 * now] > dp[now]) {
					q.push(2 * now);
					dp[2 * now] = dp[now];
				}
			}
		}
	}
}

int main()
{
	init();
	bfs();
	cout << dp[k];
}