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

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

12851번: 숨바꼭질 2

---

SOLUTION

처음엔 무작정 제출했다가 메모리 초과가 떴는데 해결하기 위해 배열 하나를 만들고 123456789로 초기화 한뒤, 이동하려는 위치 좌표의 배열값보다 이동 시간이 작거나 같으면 큐에 push해준다.

---

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAX 100001
#define INF 123456789

int n, k;
int visited[MAX], arrival[MAX];
vector<pair<int, int>>v;

void bfs(int a, int k) {
	fill(arrival, arrival + MAX, INF);
	queue<pair<int, int>>q;
	q.push(make_pair(a, 0));
	while (!q.empty()) {
		int num = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (num == k) {
			cout << cnt << '\n';
			int count = 1;
			while (!q.empty()) {
				if (q.front().first == k && q.front().second == cnt) count++;
				q.pop();
			}
			cout << count << "\n";
			return;
		}
		if (num - 1 >= 0 && !visited[num - 1]) {
			if (cnt + 1 <= arrival[num - 1]) {
				arrival[num - 1] = cnt + 1;
				q.push(make_pair(num - 1, cnt + 1));
			}
		}
		if (num + 1 < MAX && !visited[num + 1]) {
			if (cnt + 1 <= arrival[num + 1]) {
				arrival[num + 1] = cnt + 1;
				q.push(make_pair(num + 1, cnt + 1));
			}
		}
		if (num * 2 < MAX && !visited[num * 2]) {
			if (cnt + 1 <= arrival[num * 2]) {
				arrival[num * 2] = cnt + 1;
				q.push(make_pair(num * 2, cnt + 1));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	bfs(n, k);
}