[알고리즘] 백준 14403번: 경로 찾기 (C++), 경우의 수 조건

주석 조건 참고

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

queue<pair<int, int>> q;
bool visited[100001] = { 0, };

void bfs(int n, int k) {
	q.push(make_pair(n, 0));

	while (!q.empty()) {
		int value = q.front().first;
		int cnt = q.front().second;

		q.pop();

		if (value == k) {
			cout << cnt;
			return;
		}

		for (int i = 1; i <= 3; i++) {
			// 3가지의 경우를 통과하는 데에 있어서
			// 1번 조건을 만족하는 경우 for를 3번돌아도 1번조건만 통과하기 때문에
			// i == 어떠한 값이라는 조건을 걸어둠
			if (i == 1 && value - 1 >= 0 && visited[value - 1] == 0) {
				visited[value - 1] = 1;
				q.push(make_pair(value - 1, cnt + 1));
			}
			else if (i == 2 && value + 1 <= 100000 && visited[value + 1] == 0) {
				visited[value + 1] = 1;
				q.push(make_pair(value + 1, cnt + 1));
			}
			else if (i == 3 && value * 2 <= 100000 && visited[2 * value] == 0) {
				visited[2 * value] = 1;
				q.push(make_pair(2 * value, cnt + 1));
			}
		}
	}
}

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

	return 0;
}