13549번 - 숨바꼭질 3
#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
int n, k;
bool visited[100001];
void bfs() {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
visited[n] = true;
q.push({ 0,n });
while (!q.empty()) {
int cur = q.top().second;
int time = q.top().first;
if (cur == k) {
cout << time<<"\n";
return;
}
q.pop();
if (cur != 0 && cur * 2 <=100000 && !visited[cur * 2]) {
q.push({ time,cur * 2 });
visited[cur * 2] = true;
if (cur + 1 <=100000 && !visited[cur + 1]) {
q.push({(time+1), cur + 1 });
visited[cur + 1] = true;
if (cur - 1 >= 0 && !visited[cur - 1]) {
q.push({(time+1), cur - 1});
visited[cur - 1] = true;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
bfs();
return 0;
이건 성공하는데 time에 -를 붙혀서 푼건 틀리다고 나오네요
해당 코드로
시작지점 : 4, 도착지점 : 6 을 작성하게 되면 걸리는시간이 2초가 나옵니다 ( 4 - 5 - 6 ) 하지만 정답은 (4 - 3 - 6)으로 1초가 나와야합니다.
물론 단순하게 (*2, -1, +1) 순으로 검사하면 한번만 방문해서 값을 구할수 있지만
(*2, +1, -1) 순으로 검사해서 풀기위해선 여러번 방문해서 최소값의 초를 구해야합니다.
댓글을 작성하려면 로그인해야 합니다.
smc2315 2년 전
#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
int n, k;
bool visited[100001];
void bfs() {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
visited[n] = true;
q.push({ 0,n });
while (!q.empty()) {
int cur = q.top().second;
int time = q.top().first;
if (cur == k) {
cout << time<<"\n";
return;
}
q.pop();
if (cur != 0 && cur * 2 <=100000 && !visited[cur * 2]) {
q.push({ time,cur * 2 });
visited[cur * 2] = true;
}
if (cur + 1 <=100000 && !visited[cur + 1]) {
q.push({(time+1), cur + 1 });
visited[cur + 1] = true;
}
if (cur - 1 >= 0 && !visited[cur - 1]) {
q.push({(time+1), cur - 1});
visited[cur - 1] = true;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
bfs();
return 0;
}
이건 성공하는데 time에 -를 붙혀서 푼건 틀리다고 나오네요