[백준] 1697번 숨박꼭질

Peace·2021년 1월 20일

[백준] 1697번 숨박꼭질

문제 링크: https://www.acmicpc.net/problem/1697

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

문제 이해

두점이 주어진다. 한 점은 수빈이가 있는 곳이고, 다른 한점은 동생이 있는 곳이다. 동생이 숨어 있고, 수빈이가 동생이 있는 지점까지 가는 시간을 구하는 문제이다. 현재 자신의 칸이 X라면 수빈이는 X+1 이나 X-1 또는 2*X 만큼 움직일 수 있다.

문제 접근

입력 받기.

모든 Node에 3개의 branch가 있다고 생각한다. X+1, X-1, 2*X.

수빈이가 처음 들어온 지점을 0초와 함께 queue에 넣는다.

BFS진행.

현재 노드의 있는 위치와 동생의 위치와 비교하여 같으면, 현재 time에서 +1을 하고 종료.

코드 구현(c++)

#include <iostream>
#include <queue>

using namespace std;

int N, K;

typedef struct Node{
    int location;
    int time;
}node;

queue<node> q;

bool check[100001] = {false, };

int branch[3] = {1, -1, 2};

int finalTime;

void bfs(){
    node temp;
    node newNode;
    int location;
    while(!q.empty()){
        temp = q.front();
        q.pop();
        for(int i = 0 ; i < 3 ; i++){
            if(i == 2) location = temp.location * branch[i];
            else location = temp.location + branch[i];
            if(location >= 0 && location <= 100000 && !check[location]){
                if(location == K) {
                    finalTime = temp.time + 1;
                    return;
                }
                check[location] = true;
                newNode.location = location;
                newNode.time = temp.time + 1;
                q.push(newNode);

            }
        }
    }
}

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

    cin >> N >> K;
    node temp = {N, 0};
    check[N] = true;
    q.push(temp);
    bfs();
    cout << finalTime << "\n";
}