리셋 되지 말자

[백준 1697] 숨바꼭질 본문

알고리즘

[백준 1697] 숨바꼭질

kyeongjun-dev 2020. 3. 11. 16:08
#include<iostream>
#include<queue>
using namespace std;
queue<int> Q;
int *arr;
int loc= -1;
int start, target;
void BFS(void) {
	loc = Q.front();
	Q.pop();
	if (loc == target)
		return;
	if (loc > 0) {
		if (arr[loc - 1] == 0) {
			arr[loc - 1] = arr[loc] + 1;
			Q.push(loc - 1);
		}

	}
	if (loc < 100000) {
		if (arr[loc + 1] == 0) {
			arr[loc + 1] = arr[loc] + 1;
			Q.push(loc + 1);
		}

	}
	if (2 * loc < 100001) {
		if (arr[2 * loc] == 0) {
			arr[2 * loc] = arr[loc] + 1;
			Q.push(2 * loc);
		}
	}

}

int main() {
	arr = new int[100001]();
	cin >> start >> target;

	Q.push(start);
	arr[start] = 1;
	while (loc != target) {
		BFS();
	}

	cout << arr[loc] - 1;
	return 0;
}

'알고리즘' 카테고리의 다른 글

[백준] N과M(1)  (0) 2020.05.17
[백준]N와 M(1)  (0) 2020.04.25
재귀로 짠 수열(?)  (0) 2020.04.25
[백준 9466] 텀 프로젝트  (0) 2020.03.12
[백준 7576]토마토  (0) 2020.03.11
Comments