[백준][12851] 숨바꼭질2

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

12851번: 숨바꼭질 2

풀이과정

 

1. 이전 숨바꼭질1과 크게 다르지 않다. bfs를 통해 풀었다.

 

2. 한 step의 que가 비워지면 step이 증가한다. 최초로 목적지에 도달하면 최소 step이 된다.

 

최소 step으로 목적지에 방문하는 경우의 수도 구해야 한다.

 

ex) 1 4를 입력 할 경우

(1+1) * 2 = 4 

(1*2) * 2 = 4

경우의 수는 위와 같이 2가지가 나온다.

 

다음 방문 할 곳이 0이거나 현재 step과 같다면 que에 넣어주면 된다.

 

소스코드

#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;
void solution()
{
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	int count = 0;
	while (!que.empty()) {
		int queSize = que.size();
		count++;
		if (count >= MAX_VAL) {
			return;
		}
		if (visited[y] != 0) {
			break;
		}
		for (int i = 0; i < queSize; i++) {
			int cur = que.front(); que.pop();
			if (cur + 1 < MAX_VAL) {
				if (visited[cur + 1] == 0 || visited[cur + 1] == count) {
					visited[cur + 1] = count;
					que.push(cur + 1);
				}
				if (cur + 1 == y) {
					step++;
				}
			}
			if (cur * 2 < MAX_VAL) {
				if (visited[cur * 2] == 0 || visited[cur * 2] == count) {
					visited[cur * 2] = count;
					que.push(cur * 2);
				}
				if (cur * 2 == y) {
					step++;
				}
			}
			if (cur - 1 >= 0) {
				if (visited[cur - 1] == 0 || visited[cur - 1] == count) {
					visited[cur - 1] = count;
					que.push(cur - 1);
				}
				if (cur -1 == y) {
					step++;
				}
			}
		}
	}
}
int main()
{
	scanf("%d %d", &x, &y);
	if (x >= y) {
		printf("%d\n",x-y);
		printf("1\n");
	}
	else {
		solution();
		printf("%d\n", visited[y]);
		printf("%d\n", step);
	}
	return 0;
}