백준 13549 숨바꼭질3 (C++)

0-1 BFS, 다익스트라, 우선순위 큐 등 많은 방법으로 풀 수 있지만 한 번도 안해본 0-1 BFS를 사용해 풀어보았다. 이 문제의 출제 의도이자 최적화가 잘되어있어  0ms만에 문제를 풀어낼 수 있다.

0-1 BFS의 대한 알고리즘은 https://tigerfrom2.tistory.com/8

0-1 BFS 너비 우선 탐색

 

#include<iostream>
#include<algorithm>
#include<deque>

#define MAX 100001

using namespace std;

int N, M;
bool visited[MAX] = { false, };
deque<pair<int, int>> Q;
int dis[MAX] = {0,};

void BFS() {
	Q.push_front(make_pair(N, 0));
    
	while (!Q.empty()) {
		int x = Q.front().first;
		int t = Q.front().second;
	    visited[x] = true;	
		Q.pop_front();

		if (x == M) {
			cout << t;
		}

		if (x * 2 < MAX && visited[x * 2] == false) {
			Q.push_front(make_pair(x * 2, t));
			visited[x * 2] = true;
		}
if (x - 1 > -1 && visited[x - 1] == false) {
			Q.push_back(make_pair(x - 1, t + 1));
			visited[x - 1] = true;
		}
		if (x + 1 < MAX && visited[x + 1] == false) {
			Q.push_back(make_pair(x + 1, t + 1));
			visited[x + 1] = true;
		}

		
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	cin >> N >> M;

	BFS();
}

 

0-1 BFS가 어려운 알고리즘이 아니어서 구현은 빠르게 했는데 바보같이

이걸 안넣어서~~

이걸 안넣어서 1시간을 낭비했다 하 진짜... 4ms가 나온 부분은 MAX를 20000으로 해서 그런 것이고 0 ms를 뽑아낼 수 있다.