[C++] 백준 17071번 - 숨바꼭질 5 (BFS)

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

17071번: 숨바꼭질 5

 

 

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

 

 

---

 

 

접근 방법

참고 : (https://imucoding.tistory.com/736)

 

수빈이가 +1, -1로 간다는 점을 주의하자. 즉 다시 제자리로 돌아갈 수 있다! 

 

링크에서의 방법 말고 그냥 보통 BFS 방식으로 풀어서 중복으로 해당 지점에 방문하는 경우에 대해 처리를 해주지 않으면 메모리 초과가 난다. 동생의 위치는 계속해서 증가하므로 visit 배열에 "해당 지점에 도착한 최초 시간"을 저장함으로써 최초 시간 이후에 해당 지점에 도착한 경우에는 continue로 처리해준다. 

 

//
//  BFS_BOJ17071_숨바꼭질5.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <queue>
#include <utility>
#include <string.h>

using namespace std;


int visited[2][500001];

bool chk(int loc){
    if(0<=loc && loc <= 500000) return true;
    else return false;
}

int main(){
    
    int N, K;
    cin>> N >> K;

    

    queue<pair<int,int>> que;
    que.push(make_pair(N,0));
    visited[0][N] = 0;      //첫 시작 위치는 0초만에 도달
    memset(visited, -1, sizeof(visited));
    
    while(!que.empty()){
    
        int subinLoc = que.front().first;
        int subinTime = que.front().second;
        que.pop();
          
        if(chk(subinLoc)== false) continue;
        if(visited[subinTime%2][subinLoc]!=-1) continue;
        
        visited[subinTime%2][subinLoc] = subinTime; //해당 위치에 최소 몇초만에 도달했는지 저장     
        
        que.push(make_pair(subinLoc-1, subinTime+1));
        que.push(make_pair(subinLoc+1, subinTime+1));
        que.push(make_pair(subinLoc*2, subinTime+1));
    }
    
    bool flag = false;
    for(int i = 0; i<=500000; i++){
        int nextK = K + (i*(i+1))/2;
        if(nextK > 500000) break;
        if(visited[i%2][nextK] != -1 && visited[i%2][nextK] <= i) {
            cout << i << endl;
            flag = true;
            break;
        }
    }
    if(!flag) cout << -1 << endl;
    
    return 0;
}