🖊️ 문제

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

---

🖊️ 생각

이 문제를 10월?쯤에 한 번 봤었는데,
무작정 DP라고 생각했다.
그래서 너무 어렵다고 느껴서 포기했던 문제..

근데 이 문제를 우연히 만나서 다시 보니,
그래프적으로 접근해서,BFS로 풀 수 있는 문제였다.

사실 처음에는 손이 가는 DFS로.. 재귀로 열심히 풀어줬는데,
스택 오버플로우가 났다^^;;

바로BFS를 이용해서 풀어줬다.

1. x-1 / x+1 / x*2 세 방향으로 이동하도록 큐에 넣어줌
2. 방문체크는 bfs의 기본
3. 범위체크 확실히 !!

---

🖊️ 풀이

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

int n, k;
int cost[100'001];
bool visited[100'001];

void Check()
{
	queue<int> q;

	visited[n] = true;
	q.push(n);
	cost[n] = 0;
	
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		if (cur - 1 >= 0 && cur - 1 <= 100'000 && !visited[cur - 1]) {
			q.push(cur - 1);
			visited[cur - 1] = true;
			cost[cur - 1] = cost[cur] + 1;
		}
		if (cur + 1 >= 0 && cur + 1 <= 100'000 && !visited[cur + 1]) {
			q.push(cur + 1);
			visited[cur + 1] = true;
			cost[cur + 1] = cost[cur] + 1;
		}
		if (cur * 2 >= 0 && cur * 2 <= 100'000 && !visited[cur * 2]) {
			q.push(cur * 2);
			visited[cur * 2] = true;
			cost[cur * 2] = cost[cur] + 1;
		}
	}
}

int main()
{
	cin >> n >> k;

	Check();
	cout << cost[k] << endl;
}

---

🖊️ 고칠점

1. BFS, DFS 등의 그래프 문제는
   무조건 2차원 배열이 아니다.
   이런 문제도 그래프 탐색으로 풀 수 있음을 기억하자.