[백준 12851] 숨바꼭질 2 - C언어(C++)

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

12851번: 숨바꼭질 2

 문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

 

---

해당 숨바꼭질 문제는 백준 사이트 내 여러 문제가 있다. 이전에 한 번 풀었었는데, 어떤 부분이 다른지 봤더니 이 부분이 달랐다.

동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하기

 

 

눈여겨보아야할 포인트는 코드 일부분인 해당 코드.

if (pos - 1 >= 0 && !visited[pos - 1])
	q.push({ time + 1, pos - 1 });
if (pos + 1 <= MAX + 1 && !visited[pos + 1])
	q.push({ time + 1, pos + 1 });
if (pos * 2 <= MAX + 1 && !visited[pos * 2])
	q.push({ time + 1, pos * 2 });

여기서, MAX는 100,000의 수이다.

수빈과 동생 모두 100,000 이내의 위치에 있으므로 해당 범위를 벗어나지 못하게 한 것이다.

움질일 수 있는 위치에는 모두 큐에 담는다.

 

 

<< 전체 코드 >>

#include <iostream>
#include <queue>
#define MAX 100000

using namespace std;

bool visited[100001];
int minT = 987654321;
int cnt = 0;
int n, k;

void input() {
	cin >> n >> k;
}

void bfs() {
	queue<pair<int, int>> q;
	q.push({ 0,n });
	visited[n] = true;

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

		visited[pos] = true;

		if (pos == k) {
			if (minT == 987654321) {
				minT = time;
				cnt++;
			}
			else if (time == minT)
				cnt++;
		}

		if (pos - 1 >= 0 && !visited[pos - 1])
			q.push({ time + 1, pos - 1 });
		if (pos + 1 <= MAX + 1 && !visited[pos + 1])
			q.push({ time + 1, pos + 1 });
		if (pos * 2 <= MAX + 1 && !visited[pos * 2])
			q.push({ time + 1, pos * 2 });
	}
}

void sol() {
	bfs();
	cout << minT << '\n';
	cout << cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	sol();
	return 0;
}