BOJ - 숨바꼭질(1697)

BFS로 풀 수 있는 문제 입니다. 수빈이가 있는 위치 N을 시작으로 가능한 이동 거리들을 Queue에 넣어주면서 BFS로 찾아주면 됩니다. 가장 빠른 시간은 길을 찾았을 때 Graph의 Level이 됩니다.

풀이 코드

#include <stdio.h>
#define QUEUE_SIZE 200001
#define MAX_POS 200000

int N, K;

int queue[QUEUE_SIZE];
bool visited[MAX_POS];
int level[MAX_POS];
int front, rear;

void enqueue(int data) {
	queue[rear] = data;
	rear = (rear + 1);
};

int dequeue() {
	int ret = queue[front];
	front = (front + 1);
	return ret;
}

int main() {

	front = 0;
	rear = 0;

	scanf("%d %d", &N, &K);

	int cur = N;

	level[cur] = 0;
	visited[cur] = true;
	enqueue(cur);

	while (true) {

		cur = dequeue();
		if (cur == K) {
			break;
		}

		if (cur + 1 <= MAX_POS && !visited[cur + 1]) {
			level[cur + 1] = level[cur] + 1;
			visited[cur + 1] = true;
			enqueue(cur + 1);
		}
		if (cur - 1 >= 0 && !visited[cur - 1]) {
			level[cur - 1] = level[cur] + 1;
			visited[cur - 1] = true;
			enqueue(cur - 1);
		}
		if (cur * 2 <= MAX_POS && !visited[cur * 2]) {
			level[cur * 2] = level[cur] + 1;
			visited[cur * 2] = true;
			enqueue(cur * 2);
		}
	
	}

	printf("%d", level[K]);

	return 0;
}