[백준 1697] 숨바꼭질 - C++ / 알고리즘 BFS

문제

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

1697번: 숨바꼭질

딱 보았을 때 bfs 문제가 아닌 줄 알았다. 뜬끔없이 경우의 수를 일일이 다 계산해야 하는 생각이 들었다. 하지만 결국 도착지점에 접근하려는 의도는 비슷한 것 같다.

나의 코드 - bfs가 아니다....!!!

#include <iostream>
#include <queue>

using namespace std;

queue <int> q;

int hide_and_seek(int n, int k) {
	int result_time = 0;
	q.push(n);

	while (true) {
		result_time++;
		for (int i = 0;i<int(pow(3.0, result_time - 1.0));i++) {
			int now = q.front();
			if (now == k)
				break;
			q.pop();

			int next;
			next = now - 1;
			if (next >= 0 && next <= 100000) {
				q.push(next);
			}
			if (now < k) {
				next = now + 1;
				if (next >= 0 && next <= 100000) {
					q.push(next);
				}
				next = now * 2;
				if (next >= 0 && next <= 100000) {
					q.push(next);
				}
			}
		}
	}
	return result_time;
}

int main(void) {
	int n, k;
	cin >> n >> k;

	cout << hide_and_seek(n, k) << '\n';
}  

이러면 탐구했던 길을 또 탐색하게 되는 바보 같은 일이 발생한다.

그래서 갔던 길을 표시하는 bfs를 적절히 사용할 필요가 있다.

 

나의 코드 - 재도전!

참고 사이트 )  https://sihyungyou.github.io/baekjoon-1697/

단위로 나누는 발상을 했지만 좀더 세밀한 공정이 필요했다.

왜냐하면 한번 한 탐색은 다시는 탐색하지 않는 구간이므로 이를 포함시키면 안된다.

나는 참고사이트와 다르게 traverse를 하지 않았다. 여기서는 불필요해 보이고 또한 어차피 cnt가 0이면 그 다음 섹션이 없는 것이고 결국 큐가 비었다는 말이 되므로 따로 traverse를 하지 않고 cnt로 해결했다.

#include <iostream>
#include <queue>

using namespace std;

queue <int> q;
bool v[100001];  //들른 곳 표시
int result_time, cnt, seg;  // 총 걸리는 시간, 다음 섹션 카운트, 한 섹션

void hide_and_seek(int n, int k) {
	result_time = 0;
	seg = 1;

	v[n] = 1;
	q.push(n);

	while (!q.empty()) {
		cnt = 0;
		for (int i = 0;i < seg;i++) {
			int now = q.front();
			if (now == k)
				return;
			q.pop();

			int next;
			next = now - 1;
			if (next >= 0 && v[next] == 0) {
				q.push(next);
				v[next] = 1;
				cnt++;
			}
			next = now + 1;
			if (next <= 100000 && v[next] == 0) {
				q.push(next);
				v[next] = 1;
				cnt++;
			}
			next = now * 2;
			if (next <= 100000 && v[next] == 0) {
				q.push(next);
				v[next] = 1;
				cnt++;
			}
		}
		seg = cnt;
		if (cnt != 0) // cnt == 0이면 q.empty()를 의미한다.
			result_time++;
	}
}

int main(void) {
	int n, k;
	cin >> n >> k;

	for (int i = 0; i <= 100000; i++)
		v[i] = 0;

	hide_and_seek(n, k);
	cout << result_time << '\n';
}  

 

 

또는 이런 구간 상관없이 주구장창 k값이 나올 때까지 bfs를 돌리면 된다.

대신에 위치와 시간을 함께 저장해야하는 방법이다.(저번에 풀었던 스택문제와 유사한 발상이다. pair를 통해 값을 여러개 저장하는 방법!)

이러한 발상은 간단하게 풀수있는 방법 -> https://jaimemin.tistory.com/581