12851 숨바꼭질 2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

전형적인 BFS 문제인데, 몇 가지 조건이 섞여있다.

1. 가장 빠른 시간이 몇 초인지 계산
   • 이건 쉽다 그냥 BFS를 돌리면 알아서 최단거리가 나오는게 자명하니까
2. 가장 빠른 시간으로 찾는 방법의 수
   • 이 부분에서 약간 실수했는데, BFS에서 이미 방문한 칸을 재방문하지 않도록 해놔서 틀렸었다.
     그래서 재방문을 허용하지만 목표지점에 도착했을 때 최소시간을 저장하여 현재 칸이 최소시간보다 더 크면 필요없는 계산이기 때문에 버린다.
   • 목표 지점에 도착하면 걸린 시간들을 vector에 저장하고 sort하여 최소시간이랑 비교하면 방법의 수이다.

정답코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX_SIZE 100001
int field[MAX_SIZE] = { 0, };
int N, K, goal = 987654321;
int nextPos(int pos, int i)
{
	switch (i)
	{
	case 0:
		return pos + 1;
	case 1:
		return pos - 1;
	case 2:
		return pos * 2;
	}
}
int main()
{
	cin >> N >> K;
	if (N == K) {
		printf("%d\n%d\n", 0, 1);
		return 0;
	}
	field[N] = 1;
	queue<int> q;
	vector<int> v;
	q.push(N);
	
	while (!q.empty()) {
		int cur = q.front();
		int next = 0;
		q.pop();
		if (goal < field[cur]) {
			continue;
		}
		for (int i = 0; i < 3; i++) {
			next = nextPos(cur, i);
			if (next == K) {
				goal = field[cur];
				v.push_back(field[cur]);
			}
			if (next < 0 || next > MAX_SIZE) { continue; }
			if (field[next] == 0 || (field[next] >= field[cur] + 1)) {
				field[next] = field[cur] + 1;
				q.push(next);
			}
		}
	}
	sort(v.begin(), v.end());
	int result = v[0] , cnt = 0;
	for (const auto& item : v) {
		if (result == item) 
			++cnt;
		else 
			break;
	}
	printf("%d\n%d\n", result, cnt);
	return 0;
}