[C/C++] 백준 1697번 - 숨바꼭질 (BFS)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

#define MAX 100000
int N, K, ans;
int pos[100001];
queue<int> q;

void BFS(int n, int k)
{
	int cnt = 0;
	pos[n] = 1;
	q.push(n);

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

		if (now == k)
		{
			ans = cnt;
			return;
		}

		if (now * 2 <= MAX && pos[now * 2] == 0)
		{
			pos[now * 2] = pos[now] + 1;
			q.push(now * 2);
		}

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

		if (now + 1 <= MAX && pos[now + 1] == 0)
		{
			pos[now + 1] = pos[now] + 1;
			q.push(now + 1);
		}
		cnt++;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	BFS(N, K);

	cout << pos[K] - 1;

	/* pos배열 출력
	for (int i = 0; i <= 30; i++)
	{
		cout << "pos[" << i << "]" << pos[i] << endl;
	}
	*/
}

 

풀이 방법

N = 5, K = 17일때

pos[N] = 1로 하고 큐를 돌린다.

pos[5]에서 갈수있는 곳은 pos[4], pos[6], pos[10]이고 값은 pos[5]+1인 2가 된다.

pos[4]에서 갈수있는 곳은 pos[3], pos[8]이고 값은 pos[4]+1인 3이 되고,
pos[6]에서 갈수있는 곳은 pos[7], pos[12]이고 값은 pos[6]+1인 3이 되고,
pos[10]에서 갈수있는 곳은 pos[9], pos[11], pos[20]이고 값은 pos[10]+1인 3이 된다.

이런식으로 K에 도달할때까지 BFS를 실행하고 K에 도착 시 BFS 함수를 종료한다.

 

 

<좀 더 간결한 풀이 (2021.03.07)>

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

#define MAX 100000

int N, K, x;
int check[100001];
queue<pair<int, int>> q; // <위치, 시간>

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	q.push({ N,0 });

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

		check[now] = true;

		if (now == K)
		{
			cout << time;
			break;
		}

		if (now - 1 >= 0 && !check[now - 1])
			q.push({ now - 1,time + 1 });

		if (now + 1 <= MAX && !check[now + 1])
			q.push({ now + 1,time + 1 });

		if (2 * now <= MAX && !check[2 * now])
			q.push({ 2 * now,time + 1 });
	}

}

 

 

 

www.acmicpc.net/problem/1697

1697번: 숨바꼭질