[백준_1697] 숨바꼭질 c

문제

큐를 구현할 줄 알아야 해결이 가능하다 (재귀로 해결 시 stack overflow)

풀이

#include <stdio.h>
#include <stdbool.h>

#define MAX             100001
#define EXIT_SUCCESS    0
#define EXIT_FAIL       -1

// 큐 자료구조 정의
typedef struct {
    int pos;   // 현재 위치
    int steps; // 이동 횟수
} QueueNode;

typedef struct {
    QueueNode data[MAX]; // 큐 데이터 저장 배열
    int front;           // 큐의 첫 번째 요소 인덱스
    int rear;            // 큐의 마지막 요소 인덱스
} Queue;

// 큐 초기화
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 큐가 비었는지 확인
bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 큐에 삽입
void enqueue(Queue *q, int pos, int steps) {
    q->data[q->rear].pos = pos;
    q->data[q->rear].steps = steps;
    q->rear = (q->rear + 1) % MAX; // 원형 큐
}

// 큐에서 제거
QueueNode dequeue(Queue *q) {
    QueueNode node = q->data[q->front];
    q->front = (q->front + 1) % MAX; // 원형 큐
    return node;
}

int bfs(int start, int dest) {
    bool visited[MAX] = {false};
    Queue q;
    initQueue(&q);

    enqueue(&q, start, 0);
    visited[start] = true;

    while (!isEmpty(&q)) {
        QueueNode current = dequeue(&q);
        int curr = current.pos;
        int cnt = current.steps;

        if (curr == dest) {
            return cnt;
        }

        if (curr + 1 < MAX && !visited[curr + 1]) {
            visited[curr + 1] = true;
            enqueue(&q, curr + 1, cnt + 1);
        }
        if (curr - 1 >= 0 && !visited[curr - 1]) {
            visited[curr - 1] = true;
            enqueue(&q, curr - 1, cnt + 1);
        }
        if (curr * 2 < MAX && !visited[curr * 2]) {
            visited[curr * 2] = true;
            enqueue(&q, curr * 2, cnt + 1);
        }
    }

    return EXIT_FAIL;
}

int main() {
    // 0) 입력
    int n, k;
    scanf("%d %d", &n, &k);

    // 1) bfs
    printf("%d\n", bfs(n, k));

    return EXIT_SUCCESS;
}