[BAEKJOON] 1697_숨바꼭질_C언어

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

풀이

목표값으로 가기위한 최단거기를 찾는 문제로 BFS문제이다. 물론 다른 방법도 있겠지만..나는 주로 최단거리 문제는 BFS로 풀려고한다.

문제에서 말하는 1초가 추가될 때마다 1층씩 더 추가해가는 것으로 생각하고 풀면된다.

문제에서 x-1, x+1,x*2 총 3가지의 갈래가 있다. 여기서 방문했던 곳을 또 방문하여 큐에 저장하는 것은 불필요하므로 방문배열을 하나 더 만들어 방문 체크를 하도록하자.

작성한 코드

#include <stdio.h>
int N, K, L, Q[250000], visit[100001], front = -1, back = -1, count, token;
int d[100001];//층을 표시하기 위한 배열.
int main()
{
    scanf("%d %d", &N, &K);
    if (N == K)
    {
        printf("0"); return 0;
    }
    Q[++back] = N;
    while (front != back)
    {
        count++;
        front++;
        if (visit[Q[front] * 2] == 0 && (Q[front] * 2)<100001 && (Q[front] * 2 >= 0))
        {
            Q[++back] = Q[front] * 2;
            d[back] = d[front] + 1;
            visit[Q[back]] = 1;
        }
        if (Q[back] == K){ break; }
        if (visit[Q[front] - 1] == 0 && (Q[front] - 1<100001) && (Q[front] - 1 >= 0))
        {
            Q[++back] = Q[front] - 1;
            d[back] = d[front] + 1;
            visit[Q[back]] = 1;
        }
        if (Q[back] == K) { break; }
        if (visit[Q[front] + 1] == 0 && (Q[front] + 1<100001) && (Q[front] + 1 >= 0))
        {
            Q[++back] = Q[front] + 1;
            d[back] = d[front] + 1;
            visit[Q[back]] = 1;
        }
        if (Q[back] == K){ break; }
    }
    printf("%d", d[back]);
    return 0;
}