백준 1697번: 숨바꼭질 (C++)

문제 링크는 다음과 같다.

 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제 요약

- 내 위치에서 친구의 위치까지 수직선 위에서 움직이면 된다.

- 움직이는 방법은, 내 위치가 X였다면 1초 이후에 X-1, X+1, 그리고 2*X 이렇게 가능하다.

- 이때 한 번 움직일 때 1초씩 흐른다.

- 나의 위치 X에서 친구의 위치까지 이동하는 데에는 몇 초가 걸릴까?

 

 

위의 상황을 착실하게 구현해주면 된다.

 

먼저 이 문제는 기계적으로 배열 크기를 잡는 모든 이들을 위한 문제라고 할 수 있다.

 

(물론 거기에는 나도 포함되었다)

 

이 문제의 구현 수준은, 절대 24%대의 정답률이 나올만한 것이 아니다.

 

다만 대부분의 사람들이 배열의 크기를 잡을 때 n값의 범위만을 고려했기 때문에 '맞왜틀'을 반복했을 것이다.

 

 

나 또한 초반에는 그렇게 생각했다.

 

1차적으로 이것을 파악할 수 있는 부분은 문제의 힌트에 있다.

 

5에서 17을 가는 길에 18을 거친다. 이것을 보고 내가 만약에 10,0000을 목적지로 잡았다고 하면, 이 위치보다 큰 값을 거쳐서 저 위치로 다다를 가능성도 없지 않다는 것이다.

 

필자의 경우에는, 이 힌트를 보고도 이것을 파악하지 못했고, 몇 가지의 예시를 가지고 print를 찍어보는 방식으로 디버깅을 하던 도중에 깨달았다.

 

 

또, 여러가지의 예시를 넣어보는 과정을 거친 이후에도 해결되지 않는 문제들은 대부분이 극값 혹은 그 근처에서 발생하는 문제였다. 이번 경우에도 그렇다고 볼 수 있다.

 

정확한 배열 크기는 알아내지 못하였고. 그저 배열의 크기를 넉넉하게 잡아주는 방법으로 해결했다.

 

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int vis[300000];
queue<int> q;
int sec = 0;
void bfs(int start) {
	q.push(start);
	vis[start]++;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < 3; i++) {
			int np;
			if (i == 0)
				np = cur - 1;
			else if (i == 1)
				np = cur + 1;
			else
				np = 2 * cur;

			if (np < 0 || np > 100000 || vis[np] >= 0) continue;

			q.push(np);
			vis[np] = vis[cur] + 1;
			if (np == k) return;
		}
	}
}
int main(void) {
	cin >> n >> k;
	for (int i = 0; i < 300000; i++)
		vis[i] = -1;
	bfs(n);
	cout << '\n';
	for (int i = 0; i < 30; i++)
		printf("%d 에서 %d\n", i, vis[i]);
	cout << '\n';
	cout << vis[k] << '\n';
	return 0;
}