[BFS, 난이도 중] 백준 1697번 숨바꼭질

정답율은 약 24%로, 쉬운 문제는 아니다.

하지만 이 문제가 왜 BFS 알고리즘을 요하는지 이해한다면 그렇게 복잡한 문제는 아니다.

개인적으로 이 문제의 정답율이 낮은 이유는 주어진 예제가 하나 뿐인 이유도 있겠지만,

x좌표의 범위에 대한 처리가 헷갈려서 그렇다고 생각한다.

예를 들어 x좌표가 0일 경우에는 뒤로 갈 수 없고 x좌표가 50000을 초과하는 경우에는 순간 이동을 할 수 없다.

이에 대한 처리를 부가적으로 해줘야 한다.

 

이 문제는 1차원 BFS 문제이다.

수빈이의 초기 x좌표를 큐에 넣고 시작한다.

방문 여부는 time배열의 값이 0인지 아닌지를 따졌다. (0 -> 아직 방문 안함)

본인은 초기 시간을 1로 설정했기 때문에 time배열의 k(동생좌표)인덱스값 time[k] 에서 1을 뺀 값이 정답이다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int time[100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	queue<int> q;
	q.push(n);
	time[n] = 1;
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		if (t >= 1) {
			if (!time[t - 1]) {
				time[t - 1] = time[t] + 1;
				q.push(t - 1);
			}
		}
		if (t + 1 <= 100000) {
			if (!time[t + 1]) {
				time[t + 1] = time[t] + 1;
				q.push(t + 1);
			}
		}
		if (2 * t <= 100000) {
			if (!time[2 * t]) {
				time[2 * t] = time[t] + 1;
				q.push(2 * t);
			}
		}
	}
	int ans = time[k] - 1;
	cout << ans << "\n";
}