[C/C++] 백준 - 12851번 : 숨박꼭질2

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의 위치로 이동하게 된다.

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

 

너비 우선 탐색으로 갈 수 있는 모든 길은 가보면서 이미 방문했던 곳은 재방문하지 않도록 걸러주기만 하면 된다.

범위 내에 존재하는 위치이면서 아직 방문하지 않은 곳은 방문하면 되는데 여기서 생각해야할 점이 단순히 걸리는 시간을 구하는게 아니라 가장 빠른 시간이면서 다른 방법 모두를 찾아야하기에 이것을 신경써줘야한다.

 

예를 들어 현재위치가 1일 때

 

① 1 + 1 = 2

② 1 * 2 = 2

 

는 다른 방법이다. 하지만 1번을 행하면서 방문처리를 해버리면 2번이 무시되어버린다.

 

따라서 위와 같은 오류를 방지하기 위해 방문처리는 큐에서 꺼낼 때 해당 위치를 방문처리해주면 된다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, K;
bool visited[100001];

void input() {
	cin >> N >> K;
}

bool isValid(int x) {
	return (0 <= x && x <= 100000);
}

void solution() {
	queue<pair<int, int>> q;
	q.push({ N, 0 });

	int answer = 0, cnt =0; 
	bool flag = false;
	while (!q.empty()) {
		int X = q.front().first;
		int time = q.front().second;
		q.pop();

		visited[X] = true;

		if (X == K) {
			if (!flag) {
				flag = true;
				answer = time;
			}
			if (answer == time) cnt++;
		}

		if ((isValid(X - 1) && !visited[X - 1])) {
			q.push({ X - 1, time + 1 });
		}
		if ((isValid(X + 1) && !visited[X + 1])) {
			q.push({ X + 1, time + 1 });
		}
		if ((isValid(X * 2) && !visited[X * 2])) {
			q.push({ X * 2, time + 1 });
		}
	}
	cout << answer << endl << cnt << endl;
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}