[알고리즘/문제풀이][BOJ 1697번] 숨바꼭질

숨바꼭질은 너비우선탐색을 활용하여 해결할 수 있는 문제입니다. 수빈이가 이동할 수 있는 3가지 방법을 탐색 방법으로 생각하여 동생의 위치까지의 최단 거리를 계산하는 문제로 바꾸어 생각할 수 있습니다. 따라서 너비우선탐색이 사용될 수 있습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)

int N, K;

struct que {
	int x, time;
};

struct que queue[100000+20];
int wp, rp;
int visit[100000+20];

int main(void) {
	scanf("%d %d", &N, &K);

	visit[N] = 1;
	queue[wp].x = N;
	queue[wp++].time = 0;

	while (wp != rp) {
		struct que temp = queue[rp++];
		if (temp.x == K) {
			printf("%d\n", temp.time);
			return 0;
		}
		for (int i = -1; i <= 1; i = i + 2) {
			int nx = temp.x + i;
			if (nx < 0 || nx >100000) continue;
			if (visit[nx] == 1) continue;
			visit[nx] = 1;
			queue[wp].x = nx;
			queue[wp++].time = temp.time + 1;
		}
		if (2 * temp.x < 0 || 2 * temp.x >100000) continue;
		if (visit[2 * temp.x] == 1) continue;
		visit[2 * temp.x] = 1;
		queue[wp].x = 2 * temp.x;
		queue[wp++].time = temp.time + 1;
	}
}

문제의 지문은 다음 링크에서 확인할 수 있습니다.

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