[백준] 12851번 숨바꼭질 2

링크

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

12851번: 숨바꼭질 2

풀이

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

 

숨바꼭질 1에서 수빈이가 동생의 위치로 가장 빠른 시간으로 찾는 방법을 구해야 되는 게 추가되었다.

 

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

#define SIZE 100010
const int INF = 2e9;
using namespace std;

typedef long long int ll;

//움직인 횟수 , 위치에 도착 할수 있는 경우의 수
pair<int,int> v[SIZE];
queue<int> q;

int move(int here, int d) {
	if (d == 0) {
		return here-1;
	}
	else if (d == 1) {
		return here+1;
	}
	else if (d == 2) {
		return here * 2;
	}
}

void init() {
	for (int i = 0; i < SIZE; i++) {
		v[i].first = INF;
		v[i].second = 0;
	}
}

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

	init();
	int N, K; cin >> N >> K;

	if (N == K) {
		cout << 0 <<"\n"<< 1;
		return 0;
	}

	q.push(N);
	v[N].first = 0;
	v[N].second = 1;

	while (!q.empty()) {
		int h = q.front(); q.pop();
		
		for (int d = 0; d < 3; d++) {
			int n = move(h,d);

			//수빈이의 다음 위치
			if (n< 0 || n > 100000)
				continue;

			//수빈이가 가고 하는 위치 비교
			if (v[n].first >= v[h].first + 1) {
				//도착한 시간이 같다면 도착 할 수 있는 경우의 수만 증가
				if (v[n].first == v[h].first +1) {
					v[n].second += v[h].second;
					continue;
				}

				//도착한 시간이 더 짧다면 도착 시간 갱신 후 q에 push
				else if (v[n].first > v[h].first + 1) {
					q.push(n);
					v[n].first = v[h].first + 1;
					v[n].second = v[h].second;
				}
			}
		}
	}

	cout << v[K].first << "\n" << v[K].second;
	return 0;
}