백준 숨바꼭질 2 c++

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

12851번: 숨바꼭질 2

#include <iostream>
#include <queue>

using namespace std;

int n,k;
bool check[100001];
int result1 = 0;
int result2 = 0;
void bfs()
{
	queue<pair<int,int> > q;
	q.push({n,0});
	bool c = false;
	while(!q.empty()) {
		int x = q.front().first;
		int time = q.front().second;
		check[x] = true;
		q.pop();
		
		
		if(x == k && c && time == result1) {
			result2++;
			continue;
		}
		
		if(x == k && !c) {
			result1 = time;
			c = true;
			result2++;
			continue;
		}
		
		int tmp = x * 2;
		if(tmp <= 100000) {
			if(!check[tmp]) {
				q.push({tmp,time+1});
			}
		}
		
		tmp = x + 1;
		if(tmp <= 100000) {
			if(!check[tmp]) {
				q.push({tmp,time+1});
			}
		}
		
		tmp = x - 1;
		if(tmp >= 0) {
			if(!check[tmp]) {
				q.push({tmp,time+1});
			}
		}
		
	}
}


int main(void)
{
	cin >> n >> k;
	bfs();
	cout << result1 << endl << result2;
	
	return 0;
}

 

** 풀이순서

1. bfs 를 이용해 최단시간을 구한뒤 bool c 를 true로 바꿔준다 

2. (bool c  == true && time == 최단시간) 인 경우를 모두 ++ 해준다.

 

문제를 풀고난 뒤 왜 위치가 100000을 넘으면 안될지 궁금해져서 질문게시판을 찾아봤는데 같은 고민을 하는 사람이 있었습니다.

https://www.acmicpc.net/board/view/61289

글 읽기 - (궁금) 왜 100000을 넘으면 안되나요 ?

- 해서 10만 이하로 *2 를 하는것이 +를 한뒤 10만 초과로 *2 하는것보다 시간을 1초 더 적게쓸수있기 때문입니다.

 

예를들면

k = 100000, n = 50001 일 때 n*2, --, -- 인 경우보다 --,n*2 인 경우가 시간이 1 초 적게들기 때문입니다.