Baekjoon13549-숨바꼭질3

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

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다. 일반 BFS와 다르게 가중치들이 있어서 queue에서 가중치를 정해주거나 다익스트라 알고리즘을 사용해야합니다. 백준에서는 Gold5난이도를 책정하고 있다.

---

4. 생각한 것들

• 일반적인 queue, bfs로는 안풀립니다.
• dqueue로 바꿔서 풀어볼까 했지만 이것도 일반적인 방법으론 안됩니다.
• 인덱스에 가중치를 줘서 풀었습니다.
• memset이 너무 범위가 커서그런지 쓰레기값이 들어가서 배열 하나하나 MAX값을 넣어줬습니다.

---

5. code

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

const int MAX = 100001;

int n, k;
int v[MAX];

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

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

	}
}

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

	Input();
	cout << Solve();


	return 0;
}

---

6. 후기

가중치에 대한건 공부를 안했기에 어려웠다.
누가 dqueue로 풀었다고 자랑스럽게 코드를 올려놨던데… 그거 안됨.