Baekjoon12851-숨바꼭질 2

백준 사이트 12851 - 숨바꼭질 2 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
백준에서는 Gold5의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 옛날에 푼 숨바꼭질 3 코드를 참고하여 DP만 계산해주었습니다.
• n과 k가 같은 값으로 들어올 시 DP가 0으로 초기화된 상태라 0을 내뱉는 경우를 예외처리 안해줘서 틀렸습니다.

---

5. code

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

const int MAX = 100001;

int n, k;
int v[MAX];
int DP[MAX] = { 0, };
void Input()
{
	cin >> n >> k;
	for (int i = 0; i < MAX; ++i)
	{
		v[i] = 100000;
		DP[i] = 0;
	}
}

int Solve()
{
	//Bfs
	queue<int> q;
	q.push(n);
	v[n] = 0;
	while (!q.empty())
	{
		int spot = q.front();
		q.pop();

		if (spot == k)
			return v[spot];

		if (spot + 1 < MAX && v[spot + 1] > v[spot])
		{
			q.push(spot + 1);
			v[spot + 1] = v[spot] + 1;
			DP[spot + 1] ++;
		}
		if (spot - 1 >= 0 && v[spot - 1] > v[spot])
		{
			q.push(spot - 1);
			v[spot - 1] = v[spot] + 1;
			DP[spot - 1] ++;
		}
		if (spot * 2 < MAX && v[spot * 2] > v[spot])
		{
			q.push(spot * 2);
			v[spot * 2] = v[spot] + 1;
			DP[spot * 2] ++;
		}

	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	int time = Solve();
	if (n == k)
		DP[k] = 1;
	cout << time << '\n' << DP[k];


	return 0;
}

---

6. 후기

요새 자취방 이사 때문에 정신이 없어서 빠르게 풀려고 푼 문제.