BOJ (C/C++) 12851번: 숨바꼭질 2

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

12851번: 숨바꼭질 2

---

풀이

BFS를 사용하여 최솟값을 구했다.

 

방법의 가짓수를 구하기 위해 현재 저장된 시간보다 오래 걸린 노드는 탐색하지 않았고, 계산 과정 중 여러 번 탐색되는 노드는 가장 적은 값만 저장하고, 갱신 시 큐에 삽입했다.

 

이 때 적거나 같은 값도 큐에 삽입해야 최소 시간의 모든 경우를 구할 수 있다.(ex. 1-> 4 : 1+1 *2 / 1*2*2)

---

코드

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

void Find(int start, int end) {
	if (start == end) {
		printf("0\n1");
		return;
	}
	
	int min = 1000000, min_cnt = 1; // 문제에서 나올 수 없는 탐색 횟수로 초기화
	int now, next, cnt, d[3] = { -1,1 };
	int visited[100001];
	queue <int> Q;

	// 문제에서 나올 수 없는 탐색 횟수로 초기화
	fill(visited, visited + 100001, 1000000);
	Q.push(start); visited[start] = 0;

	while (!Q.empty()) {
		now = Q.front();
		Q.pop();

		d[2] = now; // *2 위치로 이동을 위해
		for (int i = 0; i < 3; i++) {
			next = now + d[i], cnt = visited[now];

			// 문제에서 주어진 범위를 벗어남 / 현재 나온 이동 횟수보다 큰 경우
			if (next < 0 || next > 100000 || visited[next] > min) continue;

			// end 지점 도달 시 값 비교 후 min 값 갱신
			if (next == end) {
				visited[next] = cnt + 1;
				if (min > visited[next]) min = visited[next], min_cnt = 1;
				else if (min == visited[next]) min_cnt++;
			}

			// 같은 위치를 여러 번 탐색할 때 가장 적은 횟수의 값만 저장되게
			else if (visited[next] >= cnt + 1) {
				visited[next] = cnt + 1;
				Q.push(next);
			}
		}
	}
	printf("%d\n%d", min, min_cnt);
}

int main() {
	int N, K;

	scanf("%d %d", &N, &K);
	Find(N, K);
	return 0;
}