[BOJ] 13549 : 숨바꼭질 3 - travelbeeee

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

---

BFS DP

 단순 BFS 탐색으로 문제를 해결하려하면, 순간이동을 하는 경우가 시간초가 0초 이므로 문제를 해결할 수 없습니다. 따라서, 순간이동을 하는 경우들을 먼저 큐에 push 해주는 방식으로 BFS 탐색을 진행하거나 혹은 BFS + DP 를 활용해서 문제를 해결 할 수 있습니다.

 

1) 순간이동을 먼저 push 해주는 방식의 BFS

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

bool visited[200000 + 1];

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

	int N, K;
	cin >> N >> K;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	visited[N] = 1;
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		if (cur.first == K) {
			cout << cur.second << '\n';
			break;
		}
		if (0 <= cur.first - 1 && !visited[cur.first - 1]) {
			q.push({ cur.first - 1, cur.second + 1 });
			visited[cur.first - 1] = 1;
		}
		if (cur.first + 1 <= K && !visited[cur.first + 1]) {
			q.push({ cur.first + 1, cur.second + 1 });
			visited[cur.first + 1] = 1;
		}
		if (cur.first * 2 <= 200000 && !visited[cur.first * 2]) {
			q.push({ cur.first * 2, cur.second });
			visited[cur.first * 2] = 1;
		}
	}
	return 0;
}

2) 이동하거나 순간이동하거나 순서를 신경쓰지 않고 BFS + DP 활용

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

int visited[200000 + 1];

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

	int N, K;
	cin >> N >> K;
	for (int i = 0; i < 200001; i++)
		visited[i] = 99999999;

	queue<pair<int, int>> q;
	q.push({ N, 0 });
	visited[N] = 0;
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		if (cur.first == K) {
			cout << visited[K] << '\n';
			break;
		}
		if (cur.first * 2 <= 200000 && cur.second < visited[cur.first * 2]) {
			q.push({ cur.first * 2, cur.second });
			visited[cur.first * 2] = cur.second;
		}
		if (0 <= cur.first - 1 && cur.second + 1 < visited[cur.first - 1]) {
			q.push({ cur.first - 1, cur.second + 1 });
			visited[cur.first - 1] = cur.second + 1;
		}
		if (cur.first + 1 <= K && cur.second + 1 < visited[cur.first + 1]) {
			q.push({ cur.first + 1, cur.second + 1 });
			visited[cur.first + 1] = cur.second + 1;
		}
	}
	return 0;
}

---