BOJ 13549, 숨바꼭질3

풀이과정

수빈이의 좌표와 동생의 좌표가 주어지고 (1차원) 수빈이는 앞뒤로 한칸씩 이동할때 1초의 시간이 소요되고 좌표값이 2배인 좌표로 이동할 때는 시간이 0초 소요된다.

따라서 이동할 수 있는 경우의 수의 가중치가 다르기 때문에 일반적인 bfs로는 접근하면 안된다..!

접근한 방법으로는 우선 큐를 선언하고 큐에 현재 좌표와(1), 순간이동할 수 있는 모든 좌표(2)를 큐에 푸시해야한다.

가능한 모든 좌표를 q에 담았다면 하나씩 pop하면서 +1, -1 좌표를 탐색한다.

탐색하면서 범위를 넘어나지 않는 좌표라면 이들도 큐에 담는다.

따라서 큐에는

1. 현재 좌표
2. 현재 좌표에서 순간이동으로 이동할 수 있는 모든 좌표들
3. +1 or -1로 이동할 때의 좌표
4. +1 or -1로 이동했을 때의 좌표에서 순간이동할 수 있는 좌표
5. …반복
   순으로 담기게 된다.

코드

#include <bits/stdc++.h>
using namespace std;

const int MX = 100001;
int sis, bro;
int board[MX];
queue<int> q;
    
void teleport(int cur){ //cur:현재 좌표
    int tmp = cur;
    if(tmp == 0) return;
    while(tmp < MX && !board[bro]){
        if(!board[tmp]){
            board[tmp] = board[cur];
            q.push(tmp);
            if(tmp == bro) return;
        }
        tmp *= 2;
    }
}

int main(){
    cin>>sis>>bro;
    board[sis] = 1;
    //수빈이가 움직일때마다 teleport가능한 좌표를 모조리 q에 넣어야함.
    q.push(sis);
    teleport(sis);
    while(!board[bro]){
        int v = q.front(); q.pop();
        vector<int> list = {v-1, v+1};
        for(int i: list){
            if(i < 0 || i >= MX) continue;
            if(board[i]) continue;
            board[i] = board[v] + 1;
            q.push(i);
            teleport(i);
        }
    }
    cout<<board[bro]-1;
}