[백준/BOJ] 12851번 숨바꼭질 2 (C++)

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

기존의 숨바꼭질 1에서는 visit 배열을 int로 선언하여 큐가 진행되면서 최소 시간을 기록했지만, 여기서는 최소 시간이 똑같이 나오는 경우의 개수도 출력해야하기 때문에 visit 배열을 bool로 선언하고, 큐가 pop을 하고 난 후 방문 처리를 해 중복 방문이 가능하게 만들었습니다. 처음에 동생을 만난 경우와 이후에 동생을 만난 경우를 구분하기 위해 cnt가 0일때 동생과 수빈이가 만났으면 처음, cnt가 0이 아니고 동생과 수빈이가 만났으면(똑같은 시간대에) 이후에 만난 걸로 처리하였습니다.

 

#include <iostream>
#include <queue>
#define MAX 200001
using namespace std;

int n, k, t, cnt;
bool visit[MAX];

void BFS() {
	queue<pair<int, int> > q;
	q.push({n, 0});
	visit[n] = true;
	while(!q.empty()) {
		int now = q.front().first;
		int time = q.front().second;
		// 똑같은 지점에 도달하는 방법이 여러개 존재할 수 있으므로 pop한 후 방문 여부 확인
        // ex) 1->(1+1=2)->(2+2=4), 1->(1*2=2)->(2*2=4)
		q.pop();
		visit[now] = true;
		
		// 똑같은 시간대에 동생 위치에 또 도착
		if(cnt && now == k && t == time) cnt++;
		
		// 처음으로 동생 위치에 도착
		if(!cnt && now == k) {
			t = time;
			cnt++;
		}
		
		if(now * 2 <= 100000 && !visit[now * 2]) q.push({now * 2, time + 1});
		
		if(now + 1 <= 100000 && !visit[now + 1]) q.push({now + 1, time + 1});
		
		if(now -1 >= 0 && !visit[now - 1]) q.push({now - 1, time + 1});
		
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	BFS();
	cout<<t<<"\n"<<cnt;
}