[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;
}Reference
この問題について([BOJ/C+]#1697鬼ごっこ), 我々は、より多くの情報をここで見つけました https://velog.io/@inryu/BOJ-C-1697-숨바꼭질テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol