백준 12851번 숨바꼭질 2 (C++)

문제

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

12851번: 숨바꼭질 2

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define CNT second
#define POS first
int N,K;
bool vis[100001];
int num_cnt[100001];
int min_cnt = 100001; //최소 거리

/* 5 17
5 10 20 19 18 17
5 6  7  8  16 17
5 6  7  8  9  18 17
5 10 9  18 17
5 10 9  8  16 17
5 4  8  16 17
*/
void	bfs(){
	queue<pair<int, int>> Q;
	Q.push({N,0});
	while (!Q.empty()){
		auto q = Q.front();
		Q.pop();
		vis[q.POS] = true;
		if (q.POS == K)
		{
			min_cnt = min(q.CNT,min_cnt);
			num_cnt[q.CNT]++;
		}else {
			if (q.CNT > min_cnt)
				continue;
			if (q.POS<100000 && !vis[q.POS+1])
				Q.push({q.POS+1,q.CNT+1});
			if (q.POS>0 && !vis[q.POS-1])
				Q.push({q.POS-1,q.CNT+1});
			if ((q.POS)*2 <=100000 && !vis[(q.POS)*2])
				Q.push({q.POS*2,q.CNT+1});
		}
	}
}

int main(){
	cin >> N >> K;
	bfs();
	cout << min_cnt << "\\n" << num_cnt[min_cnt] << "\\n";
}

풀이 과정

숨바꼭질 시리즈 문제입니다.

동생을 찾으러가는 수빈이가 가장 짧은 시간 내에 동생을 찾아야합니다.

간단한 bfs문제인데, 정답을 찾아도 해당 깊이는 전부 탐색해야만 한다는 조건을 기억하고 풀면 됩니다.

해당 조건은 이 코드로 해결했습니다.

if (q.CNT > min_cnt)
				continue;

또한 같은 깊이에서 동생을 만났을 때 횟수를 배열에 저장했었는데, 지금 생각해보니 변수로 처리해도 문제가 없겠네요.