[백준OJ] 12851번 숨바꼭질 2

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

12851번: 숨바꼭질 2

---

 

-풀이-

BFS를 이용해서 문제를 풀었다. 해당지점을 한번 도착한 뒤, 다음번에 도착하는 경우는, 시간이 더 큰 경우이므로 제외시켜주기위해 visited배열을 이용하여 해당 지점 방문 여부를 체크했고, 시간을 관리하는것이 문제였다.

BFS를 돌며 동생이 위치한 지점에 도착을 했을때의 시간이 현재 갱신된 최단 시간보다 작다면, 현재까지 구한 최단시간으로 도달할 수 있는 방법의 개수는 필요가 없어지게 되므로, 최단시간을 다시 갱신해준 뒤, 방법의 수를 1로 초기화를 해준다.

도착했을때의 시간이 현재 갱신된 최단시간과 같다면, 방법의 수를 1 증가시켜주며, 최단시간과 최단시간으로 도달 방법을 구해주면 된다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

bool visited[100001] = { 0 };
int t=987654321, cnt=0,n,k;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> k;
	queue<pair<int, int>> q;
	q.push({ n,0 });
	while (!q.empty()) {
		int now = q.front().first;
		int time = q.front().second;
		q.pop();
		visited[now] = true;
		
		if (now == k) {
			if (t > time) {
				t = time;
				cnt = 1;
			}
			else if (t == time) {
				cnt++;
			}
		}
		
		if (now * 2 <= 100000 && !visited[now * 2]) {
			q.push({ now * 2,time + 1 });
		}
		if (now + 1 <= 100000 && !visited[now + 1]) {
			q.push({ now + 1,time + 1 });
		}
		if (now - 1 >= 0 && !visited[now - 1]) {
			q.push({ now - 1,time + 1 });
		}
	}

	cout << t << "\n" << cnt << "\n";

	return 0;
}