백준(BOJ) 그래프 순회 - 숨바꼭질 (1697) - Silver 1

문제

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

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

입력

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

출력

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

예제 입력 1 

5 17

예제 출력 1 

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

문제 해결

해당 문제는 최단경로 알고리즘인 BFS를 이용하여 해결할 수 있다. BFS를 이용한 최단 경로를 위한 Distance 배열을 이용하여 주어진 조건에 맞게 이동하면서 최단경로 배열을 업데이트하는 방식으로 해결할 수 있다.

2023.08.16 - [알고리즘/그래프] - 백준(BOJ) 그래프 순회 - 미로 탐색 (2178) - Silver 1

백준(BOJ) 그래프 순회 - 미로 탐색 (2178) - Silver 1

주의해야하는 부분은 시작점과 타겟이 같은경우 잘 처리해야 한다는 점이다...

1. 주어진 조건에 맞게 N부터 시작하여 -1, +1, *2 위치로 순간이동

ll dx[3] = {-1, 1, 2}; 
//1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동

for(ll i=0; i<3; i++){
	if(i == 2)
    	newPoint = old_point * dx[i]; // 2*X 위치
    else
        newPoint = old_point + dx[i]; //  X-1 Or X+1 위치

2. Distance 맵을 Update하고 Target(K)을 찾으면 BFS 종료

if(newPoint == target) // Target을 찾으면 종료
	return ;

 

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2100000000
#define SIZE 100001

using namespace std;

typedef long long ll;
vector<ll>DISTANCE(SIZE, 0);
ll dx[3] = {-1, 1, 2}; 
//1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동

bool IndexCheck(ll point){
    if(point < 0 || point >= SIZE)
        return false;
    return true;
}

bool DisCheck(ll point, ll N){
    if(DISTANCE[point] == 0)
        return true;
    return false;
}   

void bfs(vector<ll> q, ll N, ll target){
    while(q.size() !=0){
        ll newPoint = 0;
        ll old_point = q.front();
        q.erase(q.begin());
        for(ll i=0; i<3; i++){
            if(i == 2)
                newPoint = old_point * dx[i]; // 2*X 위치
            else
                newPoint = old_point + dx[i]; //  X-1 Or X+1 위치
            
            if((IndexCheck(newPoint) == true) and (DisCheck(newPoint, N) == true)){
                DISTANCE[newPoint] = DISTANCE[old_point] + 1;
                q.push_back(newPoint);
                if(newPoint == target) // Target을 찾으면 종료
                    return ;
                
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);
    
    ll N, K;
    cin >> N >> K;
    if( N == K){
        cout << 0 << "\n";
        return 0;
    }
    
    vector<ll>q;
    DISTANCE[N] = 1;
    q.push_back(N);
    bfs(q, N, K);

    cout << DISTANCE[K]-1 << "\n";
    return 0;
}

시작점과 타켓이 같은경우 1로 처리했다가 여러번 틀림... 당연히 0이여야 하는데 실수..