1697번 숨바꼭질 - BFS

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

#define MAX_QUEUE_SIZE 100000

int memo[200000];

typedef struct _Loc
{
    int s;
    int cnt;
} Loc;

typedef struct _Queue  //큐 구현
{
    int front;
    int rear;
    Loc data[MAX_QUEUE_SIZE];
} Queue;

void init_queue(Queue *q)
{
    q->front=q->rear=-1;
}

void enqueue(Queue *q, Loc l)
{
    q->data[(++q->rear)%MAX_QUEUE_SIZE]=l;
}

Loc dequeue(Queue *q)
{
    return q->data[(++q->front)%MAX_QUEUE_SIZE];
}

int main()
{
    int N, K;  //수빈, 동생 위치
    Queue q; Loc l, m;
    
    scanf("%d %d", &N, &K);
    l.s = N, l.cnt=0;
    
    init_queue(&q);
    enqueue(&q, l);
    
    if(N<=K) {
        while(l.s != K) {
            l=dequeue(&q);
            m.cnt=l.cnt+1;
            
            if(l.s<K && !memo[l.s*2]) {
                m.s = l.s*2;  //순간이동
                enqueue(&q, m);
                memo[l.s*2]=1;
            }
            if(!memo[l.s+1]) { 
                m.s = l.s+1;  //오른쪽으로 한 칸 이동
                enqueue(&q, m);
                memo[l.s+1]=1;
            }
            if(l.s>0 && !memo[l.s-1]) {
                m.s = l.s-1;  //왼쪽으로 한 칸 이동
                enqueue(&q, m);
                memo[l.s-1]=1;
            }
        }
        printf("%d", l.cnt);
    }
    else
        printf("%d", N-K);
    
    return 0;
}

 

이 문제를 보고 BFS를 떠올려서 큐를 구현하여 풀었다. 그러나 메모리를 너무 많이 사용했기에 찝찝한 감이 있었다.

다른 사람의 코드를 보니 BFS를 안 쓰고 푼 경우도 있었다.

 

K가 2의 배수일 때는 나눠준다. K가 2의 배수가 아닐 경우에는 +1 또는 -1 한 다음 2를 나눠준 경우로 나눠진다.

ex) K가 25일 경우 N이 12이면 24, 13이면 26이 좋다.

 

K가 N의 두 배보다 작을 경우에는 N*2-K인 경우, K-N인 경우, N-2/K인 경우로 3가지가 있다. 이를 계속 재귀 시키면 메모리를 사용하지 않고 답을 낼 수 있다. 

 

 

 

참고 사이트

 

<Queue>

https://velog.io/@kysung95/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%A1%A0-C%EB%A1%9C-%ED%81%90%EB%A5%BC-%EB%A7%8C%EB%93%A4%EC%9E%90

[자료구조론] C로 큐를 만들자

<매크로>

https://coding-factory.tistory.com/695

[C언어/C++] 매크로(define) 함수 사용법 & 예제

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.