[C++] 1697: 숨바꼭질

1697: 숨바꼭질 (acmicpc.net)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

4

풀이

bfs 문제!
누적 시간과 현재 위치를 포함하는 pair를 만들어 queue에 넣어주었다.
is_visited[100001] 배열을 만들어서 방문한 곳은 표시해주어 다시 방문하지 않게 하였다.
이지이지~~

코드

#include <iostream>
#include <queue>

using namespace std;

int n, k, is_visited[100001];
queue<pair<int, int>> bfs_queue;

void set_io(void);
void input_data(void);
int bfs(void);

int main(void)
{
	set_io();
	input_data();
	cout << bfs();

	return (0);
}

void set_io(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	return ;
}

void input_data(void)
{
	cin >> n >> k;

	return ;
}

int bfs(void)
{
	bfs_queue.push(make_pair(0, n));
	is_visited[n] = 1;

	while (!bfs_queue.empty())
	{
		int now_sec = bfs_queue.front().first;
		int now_location = bfs_queue.front().second;
		bfs_queue.pop();

		if (now_location == k)
			return (now_sec);

		if (now_location <= 50000 && !is_visited[now_location * 2])
		{
			bfs_queue.push(make_pair(now_sec + 1, now_location * 2));
			is_visited[now_location * 2] = 1;
		}

		if (now_location < 100000 && !is_visited[now_location + 1])
		{
			bfs_queue.push(make_pair(now_sec + 1, now_location + 1));
			is_visited[now_location + 1] = 1;
		}

		if (now_location > 0 && !is_visited[now_location - 1])
		{
			bfs_queue.push(make_pair(now_sec + 1, now_location - 1));
			is_visited[now_location - 1] = 1;
		}
	}

	return (-1);
}

딩동댕~!~!