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에 -를 붙혀서 푼건 틀리다고 나오네요 

sdh9615   2년 전

해당 코드로

시작지점 : 4, 도착지점 : 6 을 작성하게 되면 걸리는시간이 2초가 나옵니다 ( 4 - 5 - 6 ) 하지만 정답은 (4 - 3 - 6)으로 1초가 나와야합니다.

물론 단순하게 (*2, -1, +1) 순으로 검사하면 한번만 방문해서 값을 구할수 있지만

(*2, +1, -1) 순으로 검사해서 풀기위해선 여러번 방문해서 최소값의 초를 구해야합니다.

댓글을 작성하려면 로그인해야 합니다.