[백준] 13549번*
💻 C++ 기반
✔️ 그냥 BFS는 간선마다 가중치가 다 같은 상태에서 최소 횟수를 구하는 것일뿐
✔️ 이 문제는 최소 횟수는 아니더라도 가중치가 최소일 수 있다는 것을 인지!
#include <cstdio>
#include <deque>
#include <algorithm>
#define MAX 100001
using namespace std;
int dist[MAX];
int main()
{
int N, K;
scanf("%d %d", &N, &K);
fill(dist, dist + MAX, -1);
deque<int> dq;
dq.push_back(N);
dist[N] = 0;
while (!dq.empty())
{
int cur = dq.front();
dq.pop_front();
int next;
// case 1
next = cur * 2;
if (next < MAX && dist[next] == -1)
{
dist[next] = dist[cur];
dq.push_front(next);
}
// case 2
next = cur - 1;
if (next >= 0 && dist[next] == -1)
{
dist[next] = dist[cur] + 1;
dq.push_back(next);
}
// case 3
next = cur + 1;
if (next < MAX && dist[next] == -1)
{
dist[next] = dist[cur] + 1;
dq.push_back(next);
}
}
printf("%d", dist[K]);
return 0;
}
Author And Source
이 문제에 관하여([백준] 13549번*), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-13549번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)