[백준] 1697 숨바꼭질 - C

 

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

 

---

 

BFS를 사용해 풀면 된다.

 

BFS에 대해서는 이전 글을 참고하도록 하자.

2025.05.18 - [백준] - [백준] 2178 미로 탐색 - C

[백준] 2178 미로 탐색 - C

 

---

#include <stdio.h>
#include <stdlib.h>

#define MAX 200001

int visited[MAX];
int dist[MAX];

int queue[MAX];
int front = 0;
int rear = 0;
void enqueue(int x);
int dequeue();
int is_empty();

void bfs(int n, int k);

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	bfs(n, k);
	return 0;
}
void bfs(int start, int target) {
	enqueue(start);
	visited[start] = 1;
	dist[start] = 0;
	while (!is_empty()) {
		int cur = dequeue();
		if (cur == target) {
			printf("%d", dist[cur]);
			return;
		}
		int next[] = { cur + 1, cur - 1, cur * 2 };
		for (int i = 0; i < 3; i++) {
			if (next[i] >= 0 && next[i] < MAX) {
				if (!visited[next[i]]) {
					enqueue(next[i]);
					visited[next[i]] = 1;
					dist[next[i]] = dist[cur] + 1;
				}
			}
		}
	}
}
void enqueue(int x) {
	queue[rear++] = x;
}
int dequeue() {
	return queue[front++];
}
int is_empty() {
	return front == rear;
}

 

이동할 수 있는 방향이 X-1, X+1, X*2니 이에 맞게 코드를 잘 짜주면 된다.

---