[BOJ/C++] 숨바꼭질(1697번)

1. 개요

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

1697번: 숨바꼭질

1-1. 설명

수빈이는 동생과 숨바꼭질을 한다. 수빈이는 현재 점 N에 있고, 동생은 점 K에 있다. 수빈이는 걷거나 순간이동이 가능한데, 걸을 때 1초후 +1이거나 -1 하면 된다. 순간이동을 할 때에는 *2를 해준 위치로 이동하게 된다. 수빈이와 동생 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어지며, N과 K는 0 이상 100,000 이하

---

2. 구현

2-1. 풀이

BFS를 통해서 구현해냈다. +1과 -1, *2 후의 결과를 큐에 저장하는 식으로 진행하였다. 방문하지 않은 점은 0, 방문한 점은 1 이상임을 통해 방문 여부와 이동 시간 또한 같이 저장하였다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 100001;
int queue[MAX_NUM];
int visited[MAX_NUM];

void BFS(int start, int end);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;

    BFS(N, K);
    cout << visited[K];
    return 0;
}

void BFS(int start, int end) {
    int front = -1, rear = -1;
    queue[++rear] = start;
    visited[start] = 0; // 시작점

    while (front != rear) {
        int cur = queue[++front];
        if (cur == end) break; // 현재 점이 끝점이라면 종료(start == end 조건으로 인해 추가)
        if (cur - 1 >= 0 && visited[cur - 1] == 0) { // 현재 점에서 -1 할 때
            queue[++rear] = cur - 1;
            visited[cur - 1] = visited[cur] + 1;
        }
        if (cur + 1 <= MAX_NUM && visited[cur + 1] == 0) { // 현재 점에서 +1 할 때
            queue[++rear] = cur + 1;
            visited[cur + 1] = visited[cur] + 1;
        }
        if (cur * 2 >= 0 && cur * 2 <= MAX_NUM && visited[cur * 2] == 0) { // 현재 점에서 순간이동 할 때
            queue[++rear] = cur * 2;
            visited[cur * 2] = visited[cur] + 1;
        }
    }
}