[백준 13549] 숨바꼭질 3 - C++ / 알고리즘 BFS, 우선순위 큐

문제

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

13549번: 숨바꼭질 3

나의 코드 - 틀렸다

#include <iostream>
#include <queue>

using namespace std;

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

void hide_and_seek(int n, int k) {
	v[n] = 1;
	q.push(make_pair(n,0));
	result_time = 0;
	seg = 1;

	while (!q.empty()) {
		cnt = 0;

		for (int i = 0; i < seg; i++) {
			pair<int, int> now = q.front();
			if (now.first == k) {
				result_time = now.second;
				return;
			}
			q.pop();

			int next;
			next = now.first - 1;
			if (next >= 0 && v[next] == 0) {
				q.push(make_pair(next, now.second + 1));
				v[next] = 1;
				cnt++;
			}
			next = now.first + 1;
			if (next <= 100000 && v[next] == 0) {
				q.push(make_pair(next, now.second + 1));
				v[next] = 1;
				cnt++;
			}
			next = now.first * 2;
			if (next <= 100000 && v[next] == 0) {
				q.push(make_pair(next, now.second));
				v[next] = 1;
				cnt++;
			}
		}
		seg = cnt;
	}
}

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';
}

문제점: 순간이동이 0초가 되어 각 섹션이 일정한 시간을 갖지 않는다. 그래서 아무리 빨리 도착 지점이 발견되어도 더 늦게 발견된 다른 도착 경로가 더 빠른 시간이 될 수 있는 문제가 있다. 따라서 if문에 왔을 때 return;으로 종료시키면 안되고 끝까지 큐를 돌려서 가장 작은 시간을 찾아야 한다!!!! 

 

참고 사이트) https://www.crocus.co.kr/629

(우선순위 큐로 안풀고 min으로 풀려고 했는데 도저히 나와 코드는 비슷한데 내가 왜 안되는지 모르겠다... 도대체 왜지>???)

 

또다른 문제점 : 왜 나와 코드가 비슷한데 안되는 이유를 알았다.

나는 문제 그대로 -1, +1, *2로 했는데 이러면 *2의 우선순위가 뒤로 밀린다. 즉, -1/+1에서 먼저 도착지점에 가면 *2는 이미 갔던 위치여서 가지 않게 된다. 따라서 *2를 먼저 배치하고 그다음 -1,+1 순으로 우선순위를 두고 if문을 작성해야 한다. n=1, k=2가 그 반례이다.

 

나의 코드 - min()

#include <iostream>
#include <queue>
#include <algorithm>
#include <limits.h>

using namespace std;

queue <pair<int, int> > q;  // 누적 시간, 현재 위치
bool v[100001];  //들른 곳 표시
int result_time, n, k;

void hide_and_seek() {
	v[n] = 1;
	q.push(make_pair(0, n));
	result_time = INT_MAX;

	while (!q.empty()) {
		int pos = q.front().second;
		int time = q.front().first;

		if (pos == k) {
			result_time = min(result_time, time);
		}
		q.pop();
		
		if (pos * 2 <= 100000 && v[pos * 2] == 0) {
			q.push(make_pair(time, pos * 2));
			v[pos * 2] = 1;
		}
		if (pos - 1 >= 0 && v[pos - 1] == 0) {
			q.push(make_pair(time + 1, pos - 1));
			v[pos - 1] = 1;
		}
		if (pos + 1 <= 100000 && v[pos + 1] == 0) {
			q.push(make_pair(time + 1, pos + 1));
			v[pos + 1] = 1;
		}
	}
	return;
}

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

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

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

배운점

1. min() 함수 - #include <algorithm>

2. INT_MAX - #include <limits.h> 

---

나의 코드 - "우선순위 큐"

참고사이트) https://jaimemin.tistory.com/583

우선순위 큐는 나에게 생소한 개념이었다... 결국 참고사이트를 뒤지면서 맞추는 수밖에 없었다 ㅠㅠ(언제쯤 알아서 푸는 날이 올 것인가)

일단 우선순위 큐를 사용해야 하는 이유는 이동시간이 0초인 순간이동을 우선순위로 두어야 하기 때문이다. 이는 엄밀히 따지면 BFS문제만으로 볼 수 없다. 왜냐하면 BFS는 모든 간선의 가중치가 동일하다는 전제 조건이 필요하기 때문이다. 

따라서 시간이 짧은 것/순간이동을 우선적으로 배치하여 해당 위치가 나오면 return하면 된다.

#include <iostream>
#include <queue>

using namespace std;
//우선순위 큐 - 가장 적은 시간부터 우선순위
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> >> q;  // 누적 시간, 현재 위치
bool v[100001];  //들른 곳 표시
int result_time, n, k;

void hide_and_seek() {
	v[n] = 1;
	q.push(make_pair(0, n));
	result_time = 0;

	while (!q.empty()) {
		int pos = q.top().second;
		int time = q.top().first;
		q.pop();

		if (pos == k) {
			result_time = time;
			return;
		}

		if (pos * 2 <= 100000 && v[pos * 2] == 0) {
			q.push(make_pair(time, pos * 2));
			v[pos * 2] = 1;
		}
		if (pos - 1 >= 0 && v[pos - 1] == 0) {
			q.push(make_pair(time + 1, pos - 1));
			v[pos - 1] = 1;
		}
		if (pos + 1 <= 100000 && v[pos + 1] == 0) {
			q.push(make_pair(time + 1, pos + 1));
			v[pos + 1] = 1;
		}
	}
}

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

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

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

 

이 코드 또한 *2를 먼저 if문에 배치해야한다. 이를 못차서 한동안 틀렸다...ㅠ