[C++] 백준 12851번 숨바꼭질 2

그래프 탐색 문제.

BFS 너비 우선탐색을 통해서 풀면 되는 문제다.

조건이 꽤 까다로운 문제다. 다른 그래프 탐색 문제들처럼 풀면

메모리 초과가 난다.

 

문제풀이

예전에 숨바꼭질1을 풀었었는데, 그 때는 그냥 가장 빠르게 목적지에 도달한 경우 

몇 초인지만 알면 되는 문제였다.

이 문제는 가장 빠르게 목적지에 도달한 경우가 몇 초이고, 그 시간대로 가는 경우가

몇 가지가 존재하는지 출력하면 된다.

 

조건은 짜기 나름이므로, 코드 전문을 보고 틀린 이유만 정리하겠다.

 

/*
* 백준 12851번 숨바꼭질 2
* https://www.acmicpc.net/problem/12851
* 그래프 탐색 이론 - 너비 우선 탐색(BFS)
*/
#include <iostream>
#include <queue>
using namespace std;

int startSubinPoint, broPoint;
bool findBro;
int pointTime[100001];
int ansTime = 100000000;
int ansCnt;

void bfs() {
	queue<pair<int, int>> q;
	q.push({ 0, startSubinPoint });
	while (!q.empty()) {
		int curTime = q.front().first;
		int curPoint = q.front().second;
		q.pop();

		pointTime[curPoint] = curTime;

		if (findBro && curTime > ansTime) {
			continue;
		}

		if (curPoint == broPoint) {
			findBro = true;
			ansTime = curTime;
			ansCnt++;
			continue;
		}

		/*
		* 틀린 이유 : 갈 수 있는 칸에 대한 조건을 잘못 설정했었다.
		* 1. 방문한 곳은 가지 않도록 만들었음. <- 이 경우, 다르게 갈 수 있는 경우도 가지 못하게 만든다.
		* 2. 해당 칸에 가는 시간이 정답이 된 시간보다 작을 때만 가도록 만듦
		* ㄴ> 이 경우, 가는 경우가 ㅌ더하기, 빼기를 많이 해야할 경우 많은 중복탐색이 발생한다.
		* 
		* 해결책 : 각 칸마다 각 칸에 도달했을 때의 시간을 저장해두고 그 시간보다 적거나 같은 경우만 가도록 한다.
		*/
		if (curPoint - 1 >= 0 && (pointTime[curPoint - 1] == 0 || curTime + 1 <= pointTime[curPoint - 1])) {
			q.push({ curTime + 1, curPoint - 1 });
		}

		if (curPoint + 1 <= 100000 && (pointTime[curPoint + 1] == 0 || curTime + 1 <= pointTime[curPoint + 1])) {
			q.push({ curTime + 1, curPoint + 1 });
		}

		if (curPoint * 2 <= 100000 && (pointTime[curPoint * 2] == 0 || curTime + 1 <= pointTime[curPoint * 2])) {
			q.push({ curTime + 1, curPoint * 2 });
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
		
	cin >> startSubinPoint >> broPoint;

	bfs();

	cout << ansTime << "\n" << ansCnt;

	return 0;
}

주석에도 나와있듯이 내가 틀렸던 이유를 정리해 보겠다.

• 방문한 곳을 다시 가지 않도록 만들었었다. 이 경우, 해당 칸까지 가는 경로가 여러 개가 생길 수 있는데 이런 경우들은 다 무시하게 된다.
• 해당 칸에 가는 시간이 정답이 된 시간보다 작을 때만 가도록 만들었었다. 이 때 최초의 정답이 된 시간 값을100,000,000으로 초기화했었는데, 이 경우 +1, -1이 상당히 중복되게 탐색하므로 메모리 초과가 발생한다.

 

따라서 위 두 가지 문제를 해결하는 해결책이 필요했다.

해결책은 각 칸마다 도달한 시간을 저장해두고 그 시간보다 적거나 같은 경우만 해당 칸에 가도록 하면 된다.

(아마 적게 가는 경우는 없을 것이다. BFS로 해당 칸을 이미 도달했다면 그 시간초보다 같을 수는 있어도 더 작을 수는 없다. 실제로도 위 조건에서 현재 시간 + 1 == 다음 칸의 저장된 시간 으로 만들어도 맞았다고 나온다.

 

 

GitHub - kimyunseok/cpp: my study-record

코드는 위에서 확인이 가능하다.