[BOJ/C+]#1697鬼ごっこ

問題を解く

初めてdfsで解いた時に止まった区間はN=Kの時だけだったので、とても...まだ終わっていません.
bfsで解決する.
<スビンの位置、時間>pairをqueueに格納します.
ポップ・スビンのペアが弟と同じ位置にあるときは、時間を逆転すればいいです.
時間が少ないからQに入るので初めて出るのが一番早い時間です
弟を見つける前に、3つのケースを順番にキューに入れて進めばいい!while(!q.empty())..
この問題でも最短距離を歩かなければならないので、visitedを利用してアクセスしたことのない場所をキューに再入れするしかありません.

コード#コード#

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100000
int visited[MAX+1];

int bfs(int N,int K) {
    queue<pair<int, int>> q; // 수빈이 위치, 시간
    q.push(make_pair(N, 0));
    visited[N] = true;

    while (!q.empty()) {
        int loc = q.front().first;
        int time = q.front().second;
        q.pop();

        // 동생을 찾았을 때
        if (loc == K)
            return time;

        // 3가지 경우
        // 방문하지 않은 곳만! (방문한 곳에 다시 가면 최단 거리 X)
        if (loc - 1 >= 0 && !visited[loc - 1]) {
            q.push(make_pair(loc - 1, time + 1));
            visited[loc - 1] = true;
        }
        if (loc + 1 <= MAX && !visited[loc + 1]) {
            q.push(make_pair(loc + 1, time + 1));
            visited[loc + 1] = true;
        }

        if (loc * 2 <= MAX && !visited[loc * 2]) {
            q.push(make_pair(loc * 2, time + 1));
            visited[loc * 2] = true;
        }
    }
}
int main(){

    int N,K;
    cin>>N>>K;
    cout<<bfs(N,K)<<"\n";

    return 0;
}