[C++] 백준 12851번: 숨바꼭질 2

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

12851번: 숨바꼭질 2

1. 문제풀이

 위치가 X일 때 X-1 또는 X+1로 이동하거나 2*X의 위치로 순간이동할 경우 1초가 소모된다. 이동 방법은 3가지임을 알 수 있으며 동일한 시간이 소모됨을 확인할 수 있다. 각 방법에 대하여 시간이 1초가 소모되는 가중치가 동일한 상황이므로 너비 우선 탐색을 시행하여 최단 시간을 구한다. 현재 위치에서 각 방법으로 이동 한 결과를 큐에 넣은 후, 목표 위치에 도달하면 해당 시간을 저장하고 결괏값을 1증가시킨다. 큐에 남아있는 정보에서 이동 시 목표 위치에 도달할 경우 결괏값을 1증가시키고, 목표 위치에 도달한 시간이 저장된 시간을 초과하면 너비 우선 탐색을 종료한다.

2. C++ 코드

#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>

using namespace std;

int res, cnt;
int visited[100001];

void search(int from, int to)
{
	queue<pair<int, int>> q;
	q.push(make_pair(0, from));
	while (!q.empty()) {
		int time = q.front().first;
		int pos = q.front().second;
		visited[pos] = 1;
		q.pop();
		if (pos == to) {
			res = time;
			cnt++;
		}
		if (visited[to] && res < time) {
			return;
		}
		if (pos - 1 >= 0 && !visited[pos - 1]) {
			q.push(make_pair(time + 1, pos - 1));
		}
		if (pos + 1 <= 100000 && !visited[pos + 1]) {
			q.push(make_pair(time + 1, pos + 1));
		}
		if (pos * 2 <= 100000 && !visited[pos * 2]) {
			q.push(make_pair(time + 1, pos * 2));
		}
	}
}

int main(void)
{
	int n, k;
	scanf("%d %d", &n, &k);
	search(n, k);
	printf("%d\n%d\n", res, cnt);

	return 0;
}