BOJ 백준 13549 : 숨바꼭질 3

시작하면서

　이번 문제는 다익스트라 알고리즘(Dijkstra Algorithm) 을 사용해 해결하는 문제이다.

BOJ 13549 - 숨바꼭질 3

​

문제 이해

​ 이 문제는 언뜻보면 다익스트라인지 아닌지 알기 애매한 문제이다. 노드와 간선이 제시되어 있지 않고, 단순히 이동해야 한다고 제시되어 있기 때문이다. 이 문제를 다음과 같이 해석해야 한다.

• 수빈이와 동생의 위치는 노드이다.
  • 그러므로 노드가 0번부터 ~ 100,000번까지 있다고 생각하면 된다.
  • 이때 100,000을 넘어가면 가장 빠른 시간이 되지 않고 더 늘어나기만 하므로, 문제에서 제시하지 않았지만 100,000 이상의 범위는 무시한다.
• 이동할 수 있는 경우의 수는 총 3가지로 x2, -1, +1이다.
  • 해당 경우의 수로 이동하는 경로들이 모두 간선이다.

​ 위와 같이 문제를 변경하고 최소 경로를 찾아간다. 방법은 다음과 같다.

1. 현재 수빈이의 위치를 deque에 넣어준다.

2. 현재 노드에서 이동할 수 있는 경우의 수들을 체크한다.

   • 중요 : x2로 이동하는 경우는 시간이 올라가지 않으므로, 먼저 체크하기 위해 큐의 앞에 넣어주고, 한 칸씩 이동하는 경우는 큐의 뒤에 넣어준다.

   • 0 ~ 100,000 사이에 있는지, 이미 방문한 점인지를 체크하고 조건에 만족하면 큐에 넣어준다.

3. 계속 반복하면서 답을 찾는다.

​

해결

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>

using namespace std;

#define RANGE (100001)

bool IsOverNumer(int standard, int number)
{
	if (number > 100000)
		return true;

	if (number < 0)
		return true;

	return false;
}

int GetAnswer(int N, int K)
{
	if (N == K)
		return 0;

	vector<bool> visited(RANGE, false);
	deque<pair<int, int>> q;

	q.push_front(make_pair(N, false));
	while (q.empty() == false)
	{
		int current = q.front().first;
		int time = q.front().second;

		if (current == K)
		{
			return time;
		}

		q.pop_front();

		if (IsOverNumer(K, current * 2) == false && visited[current * 2] == false)
		{
			visited[current * 2] = true;
			q.push_front(make_pair(current * 2, time));
		}

		if (IsOverNumer(K, current - 1) == false && visited[current - 1] == false)
		{
			visited[current - 1] = true;
			q.push_back(make_pair(current - 1, time + 1));
		}

		if (IsOverNumer(K, current + 1) == false && visited[current + 1] == false)
		{
			visited[current + 1] = true;
			q.push_back(make_pair(current + 1, time + 1));
		}
	}

	return 0;
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	int N, K;

	cin >> N >> K;

	cout << GetAnswer(N, K);

	return 0;
}