[백준][1697] 숨바꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

풀이과정

 

1. x + 1, x -1, x *2의 이동방향을 가지는 주인공이 도착지에 도착하는 가장 빠른 길이를 구하는 문제이다.

 

2. bfs를 통하여 문제를 풀었다.

 

3. que를 비워줄때 마다 step이 증가하고 최초로 visited[목적지]를 방문하는 step이 정답이 된다.

 

 

 

소스코드

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#define MAX_VAL 100001
using namespace std;
int x, y;
int visited[100001];
int step = 0;
int solution()
{
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	int count = 0;
	while (!que.empty()) {
		int queSize = que.size();
		count++;
		if (visited[y] != 0) {
			break;
		}
		for (int i = 0; i < queSize; i++) {
			int cur = que.front(); que.pop();
			if (cur + 1 < MAX_VAL && visited[cur + 1] == 0) {
				visited[cur + 1] = count;
				que.push(cur + 1);
			}
			if (cur * 2 < MAX_VAL && visited[cur * 2] == 0) {
				visited[cur * 2] = count;
				que.push(cur * 2);
			}
			if (cur - 1 >= 0 && visited[cur - 1] == 0) {
				visited[cur - 1] = count;
				que.push(cur - 1);
			}
		}
	}
	return visited[y];
}
int main()
{
	scanf("%d %d", &x, &y);
	if (x == y) {
		printf("0\n");
	}
	else {
		printf("%d\n", solution());
	}
	return 0;
}