[Baekjoon] 백준 1697번 숨바꼭질

1697번 숨바꼭질 문제 풀이

문제

• 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
  수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

• 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제

입력
5 17

출력
4

코드

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

const int MAX = 100001;
int road[MAX];
bool check[MAX];
int n, k;
queue<int> q;
void bfs() {
    while (!q.empty()) {
        int nx = q.front();
        q.pop();
        if (nx - 1 >= 0) {
            if (check[nx - 1] == false) {
                check[nx - 1] = true;
                road[nx - 1] = road[nx] + 1;
                q.push(nx - 1);
            }
        }
        if (nx + 1 < MAX) {
            if (check[nx + 1] == false) {
                check[nx + 1] = true;
                road[nx + 1] = road[nx] + 1;
                q.push(nx + 1);
            }
        }
        if (nx * 2 < MAX) {
            if (check[nx * 2] == false) {
                check[nx * 2] = true;
                road[nx * 2] = road[nx] + 1;
                q.push(nx * 2);
            }
        }
    }
}

int main() {
    cin >> n >> k;
    road[n] = 0;
    check[n] = true;
    q.push(n);
    bfs();
    cout << road[k] << endl;
    return 0;
}

해결방법

변수	내용
road[]	이동 시간
check[]	탐색 여부
n	수빈위치
k	동생위치

• 시작 위치의 이동 시간을 '0'초로 지정한 후 check[시작위치]를 true로 선언, q에 n을 집어넣고 bfs탐색을 시작한다.
• 수빈이가 이동할 수 있는 위치의 조건은 n-1, n+1, n*2 세가지로 정의되어있다.
• 시작 위치에서 세가지 조건에 해당하는 알맞는 범위를 조건문으로 넣어주며 road[]의 값을 시작 위치 road[]값에서 1씩 증가시키며 모든 거리에 대해 이동 시간을 적어준다.
  1. 이미 확인된 거리는 다시 확인하지 않는다.
• 모든 탐색이 끝난 후에 road[k]값을 출력한다.