[백준] 1697- 숨바꼭질(C++)

문제링크:www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

너무나도 간단한 bfs 문제입니다.

 

숫자 범위가 크기 때문에 bfs를 선택했고, 방문여부를 판단하는 배열을 만들어서 문제를 해결했습니다.

 

아래는 정답 코드입니다.

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

int n = 0, k = 0;
int result = 0;
int visited[100001] = { 0, };
queue <int> que;

int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;

	que.push(n);
	visited[n] = 1;
	while (!que.empty()) {
		int p = que.front();
		que.pop();
		if (p == k) {
			cout << visited[p] - 1 << endl;
			return 0;
		}
		if (visited[p - 1] == 0 && (p - 1) >= 0 && (p - 1) <= 100000)
			que.push(p - 1), visited[p - 1] = visited[p] + 1;
		if (visited[p + 1] == 0 && (p + 1) >= 0 && (p + 1) <= 100000)
			que.push(p + 1), visited[p + 1] = visited[p] + 1;
		if (visited[p*2] == 0 && (p*2) >= 0 && (p*2) <= 100000)
			que.push(p*2), visited[p*2] = visited[p] + 1;
	}

	return 0;
}