백준 - 1697 숨바꼭질

 

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

본 문제는 출발지에서 도착지 까지 갈수 있는 방법 ( +1, -1, *2 ) 을 각각 계산하여 BFS 방식으로 반복하여 목적지에 도달하는데 걸리는 시간을 산출할 수 있다.

 

알고리즘은 다음과 같다.

 

1. 현재위치를 시작위치로 잡고 현재 위치를 큐에 넣는다.

2. 큐에서 한 지점을 꺼내 현재 위치로 설정한다.

3. 해당 지점이 방문되지 않았다면 현재위치에서 +1 지점을  큐에 넣는다.

4. 해당 지점이 방문되지 않았다면 현재 위치에서 -1 지점을 큐에 넣는다.

5. 해당 지점이 방문되지 않았다면 현재 위치에서 *2 지점을 큐에 넣는다.

6. 목적지에 도달할때 까지 2~5 단계를 반복한다.

 

한번 방문한곳을 다시 방문할 필요가 없기때문에 최대 100,000 번 만 방문하면 되기 때문에 O(n) 의 성능을 기대할 수 있다.

알고리즘 대로 구현한 코드는 아래와 같다.

 

단 각 위치별 값의 의미는 아래와 같다.

0: 미방문

1 ~ N : 시작위치에서 현재 위치까지 오는데 걸린 시간 + 1

 

구현된 코드는 아래와 같다

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool checkAndPush(vector<int> &m, queue<int> &q, int cur, int next, int &dest);

int main()
{
	vector<int> m(100001, 0);

	int s, e;

	cin >> s >> e;

	queue<int> q;
	q.push(s);

	int count = 1;
	m[s] = count;

	if (s == e)
	{
		cout << 0 << endl;
		return 0;
	}

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		if (checkAndPush(m, q, cur, cur + 1, e)) return 0;
		if (checkAndPush(m, q, cur, cur - 1, e)) return 0;
		if (checkAndPush(m, q, cur, cur * 2, e)) return 0;
	}
	cout << "Error" << endl;
}

bool checkAndPush(vector<int> &m, queue<int> &q, int cur, int next, int &dest)
{
	if (next < 0 || next > 100000) return false;
	if (m[next] != 0) return false;

	if (next == dest)
	{
		cout << m[cur] << endl;
		return true;
	}

	m[next] = m[cur] + 1;
	q.push(next);
	return false;
}