ShaShaKa Dev Note

숨바꼭질

20 October 2019

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

이번은 또 다른 BFS 최단거리 연습문제를 풀어보도록 하겠습니다.

#include<stdio.h>

static int N, K;

int head = 0;
int tail = 0;
int visit[100001] = { 0 };
const int arr_size = 1000001;

void bfs();

struct Node
{
	int x, y;
	Node* myAlloc(int x, int y) {
		this->x = x;
		this->y = y;
		return this;
	}
}a[arr_size];

void add(int x, int y) {
	if (tail >= arr_size)
	{
		tail -= arr_size;
	}
	a[tail++].myAlloc(x, y);
}

Node* pull() {
	if (head == tail)
	{
		return NULL;
	}
	if (head >= arr_size)
	{
		head -= arr_size;
	}
	return &a[head++];
}


int main(void) {

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

	add(N, 0);

	bfs();
}

void bfs() {

	Node* node = pull();

	while (node != NULL)
	{

		if (node->x == K)
		{
			printf("%d", node->y);
			return;
		}

		if (node->x - 1 >= 0 && visit[node->x - 1] == 0)
		{
			visit[node->x - 1]++;
			add(node->x - 1, node->y + 1);
		}

		if (node->x + 1 <= 100000 && visit[node->x + 1] == 0)
		{
			visit[node->x + 1]++;
			add(node->x + 1, node->y + 1);
		}

		if (node->x != 0 && node->x * 2 <= 100000 && visit[node->x *2] == 0)
		{
			visit[node->x *2]++;
			add(node->x * 2, node->y + 1);
		}

		node = pull();
	}
}

먼저 Node를 선언하여, Circullar Queue를 생성하여 줍니다.
가장 먼저, 큐에 최초 시작하는 지점을 x, 현재 이동한 카운트, 즉 처음에는 0을 넣어줍니다.
이동 가능한 위치는 x-1, x+1, 2*x 가 있는데, 이동 범위의 제한이 있으니 해당 범위를 체크해서 해당 범위 이내일 때에만 큐에 넣어주도록 합니다.
그리고, 메모리 초과를 막기 위해서 이미 한 번 방문한 위치는 다시 넣지 않습니다.
해당 로직을 수행하면서, 최종 도착지점이 나오면 이동 카운트를 출력해주도록 합니다.