[백준 / C++] 13549 숨박꼭질 (3) - (1)

백준 13549번 숨박꼭질 3 문제  

문제

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

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

입력

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

출력

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

예제 입력 1 

5 17

예제 출력 1

2

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

 

---

 

숨박꼭질 3 문제 풀이

 

이 문제는 BFS 알고리즘을 사용해서 풀 수 있다. 먼저 문제의 조건을 살펴보자.

 

조건 1. 

거리의 2배를 할 때는 point 가 늘어나지 않는다.

 

조건 2.

거리 + 1, -1 할 때는 point + 1을 한다. 

 

이렇게 기본 조건을 세우면 되는데, 이 문제는 예외 조건이 특히나 더 중요한 문제이다.

먼저 BFS 를 하지만, 방문 상태 체크를 해야한다. 그래서 2가지 조건을 들여 que에 추가해주는 경우를 세웠다.

 

예외 조건 1. 거리가 2배 상황일 때

거리가 2배일 때 너무 커지면 안되는 상황을 대비해 (X * 2 < 101000)인 상황을 주었다. 

	if (X * 2 < 101000) {
		if (check[X * 2] == 0) {
			que.push({ X * 2, point });
			check_point[2 * X] = min(check_point[2 * X], point);
		}
		else if (check[X * 2] == 1 && point < check_point[2 * X]) {
			que.push({ X * 2, point });
			check_point[2 * X] = min(check_point[2 * X], point);
		}
	}

 

예외 조건 2. 이미 방문한 상태지만, 만약 방문했을 때보다 point가 적을 때

이 때는 que에 추가해주는 상황을 제시했다

if (check[X - 1] == 0) { // 방문 안했을 경우
	que.push({ X - 1 , point + 1 });
	check_point[X - 1] = min(check_point[X - 1], point + 1);
}
else if (check[X - 1] == 1 && point + 1 < check_point[X - 1]) { // 방문했지만 , 더 적은 point일 경우
	que.push({ X - 1 , point + 1 });
	check_point[X - 1] = min(check_point[X - 1], point + 1);
}

 

---

 

숨박꼭질 3 전체 코드 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
queue<pair<int,int>> que;
bool check[101001] = { 0 };
int check_point[101001] = { 0 };

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int N, K;
	cin >> N >> K;
	int result = 999999;
	if (N > K) {
		result = N - K;

		cout << result;
		return 0;
	}

	fill(check_point, check_point + 101001, result);

	que.push({ N,0 });

	while (!que.empty()) {
		int X = que.front().first;
		int point = que.front().second;
		//cout << " X : " << X << " , point : " << point << " , result : " << result << '\n';
		que.pop();

		check[X] = 1;

		if (point > result) continue;

		if (X == K) {
			result = min(result, point);
			cout << result;
			return 0;
		}
		if (X < 0 || X > 100001) continue;

		if (X > K) {
			int max_point = point + X - K;

			result = min(result, max_point);
			continue;
		}
		else {
			if (X * 2 < 101000) {
				if (check[X * 2] == 0) {
					que.push({ X * 2, point });
					check_point[2 * X] = min(check_point[2 * X], point);
				}
				else if (check[X * 2] == 1 && point < check_point[2 * X]) {
					que.push({ X * 2, point });
					check_point[2 * X] = min(check_point[2 * X], point);
				}
			}
			
			if (check[X - 1] == 0) {
				que.push({ X - 1 , point + 1 });
				check_point[X - 1] = min(check_point[X - 1], point + 1);
			}
			else if (check[X - 1] == 1 && point + 1 < check_point[X - 1]) {
				que.push({ X - 1 , point + 1 });
				check_point[X - 1] = min(check_point[X - 1], point + 1);
			}
			if (check[X + 1] == 0) {
				que.push({ X + 1, point + 1 });
				check_point[X + 1] = min(check_point[X + 1], point + 1);
			}
			else if (check[X + 1] == 1 && point + 1 < check_point[X + 1]) {
				que.push({ X + 1, point + 1});
				check_point[X + 1] = min(check_point[X + 1], point + 1);
			}
			
		}
	}

	cout << result;

	return 0;
}