알고리즘(C++) / 백준 1697 : 숨바꼭질

1697 : 숨바꼭질

http://boj.kr/1697

1697번: 숨바꼭질

 

문제

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

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

 

입력

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

 

출력

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

 

코드

//1697 숨바꼭질
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int N, K;
int time = 0;
bool visited[100001] = { false, };
void BFS() {
	queue <pair<int,int>> q;
	q.emplace(0, N);

	while (!q.empty()) {
		int next = q.front().second;
		visited[next] = true;
		if (next == K) {
			time = q.front().first;
			return;
		}
		int next_time = q.front().first + 1;

		if (next * 2 < 100001) {
			if (visited[next * 2] == false)
				q.emplace(next_time, next * 2);
		}
		if (next + 1 < 100001) {
			if (visited[next + 1] == false)
				q.emplace(next_time, next + 1);
		}
		if (next - 1 >= 0) {
			if (visited[next - 1] == false)
				q.emplace(next_time, next - 1);
		}

		q.pop();

	}
}

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

	cin >> N >> K;

	if (N >= K) {
		time = (N - K);
	}
	else
		BFS();

	cout << time << "\n";

	return 0;
}

 

설명

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

가장 빠른 시간을 찾기 위해서는 BFS(넓이 우선 탐색)를 사용한다.

수빈이는 +1, -1, x2 위치로 이동할 수 있다. 수빈이 위치가 동생 위치보다 큰 경우와 작은 경우로 나눠서 생각할 수 있다.

 

수빈이 위치가 동생 위치보다 큰 경우

수빈이는 작은 곳으로 이동하는 방법은 -1 하는 방법뿐이다. 그래서 이 경우에는 수빈이 위치 - 동생 위치해주면 된다. 

 

수빈이 위치가 동생 위치보다 작은 경우

BFS를 사용하여 수빈이가 이동할 수 있는 위치를 queue에 pair 쌍으로 수빈이 위치로부터의 거리와, 위치를 저장한다.

수빈이가 이동하는 방법은 +1, -1, x2 하는 경우이다. 이때 이동할 위치가 이미 전에 방문하였거나 0보다 작거나 100000보다 크다면 이동하지 못한다. 

이때 동생의 위치를 방문하게 되면 종료하고 시간을 출력할 수 있다.

 

 

결과

 

고찰

queue에서 emplace 함수를 처음 사용해보았다.

emplace는 값을 만드는 생성자 인수를 전달해주면 그 인수들로 새로 원소가 들어갈 장소에 바로 원소를 만든다. 즉, 들어갈 값을 생성자로 생성한 다음에 그것을 복사해 새로 컨테이너에 넣는 메모리 낭비를 막아준다.

emplace는 push와 기능적으로 거의 동일한 역할을 한다.

위에서 처럼 pair를 사용할 경우에는 emplace를 사용하는 것이 깔끔하고 효율적이다.

q.emplace(0, N);
q.push(make_pair(0, N));

push는 pair 쌍을 만들어준 후 push를 해주어야 하지만 emplace는 pair 쌍을 만들어주지 않고 사용 가능하다.

 

난이도

●●○○○