백준 1697 숨바꼭질 (C++)

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>

#define MAX 51

using namespace std;

queue<pair<int, int>> Q;
int x, y;
bool visited[100001] = {false,};

void BFS() {

	Q.push(make_pair(x, 0));
	visited[x] = true;
	while (!Q.empty()) {
		int X = Q.front().first;
		int T = Q.front().second;
		
		Q.pop();

		if (X == y) {
			cout << T << '\n';
			return;
		}

		if (X + 1 > -1 && X + 1 < 100001 && visited[X + 1] == false) {
			Q.push(make_pair(X + 1, T + 1));
			visited[X + 1] = true;
		}

		if (X - 1 > -1 && X - 1 < 100001 && visited[X - 1] == false) {
			Q.push(make_pair(X - 1, T + 1));
			visited[X - 1] = true;
		}

		if (2 * X < 100001 && visited[2 * X] == false) {
			Q.push(make_pair(2 * X, T + 1));
			visited[2 * X] = true;
		}
	}
}

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

	BFS();
}

 DFS , BFS 는 비단 그래프에만 국한되어있지 않다. 이걸 ? 하는 부분에서도 BFS DFS는 유용하게 사용된다. 순열조합의 DFS가 그렇고 최소최단거리를 구하는 BFS가 그렇다. 

이 문제 또한 BFS 문제구나! 를 아는 것이 중요하다. 그렇다면 어떻게 이것을 BFS 문제라고 인식해야할까? 나같은 코린이는 이것 부터가 문제였다.

 

1. 주어진 조건을 본다.

2. 수빈이는 x+1, x-1, 2*x 이렇게 세가지 행동을 할 수 있다. 이것을 보고 "아 계속해서 세가지 조건을 고수해나가는구나!" 라고 판단하고 그래프 처럼 생각할 수 있음을 캐치해야한다.

3. 큐를 생성하여 각 행동을 넣고 BFS하며 목표와의 최소 거리를 출력한다.