문제
풀이
N 인덱스에서 K 인덱스까지 찾아가는 최소 시간을 구하는 문제입니다.
만약 현재 위치가 X라면 X+1, X-1 의 위치로 1초의 시간으로 이동할 수 있고,
X*2의 위치로는 0초의 시간으로 이동할 수 있습니다.
이 문제는 bfs로도 풀 수 있지만 다익스트라 알고리즘으로도 풀 수 있습니다.
저는 다익스트라 알고리즘으로 풀이해봤습니다.
다익스트라는 graph에서 노드들의 최소경로를 구하는 알고리즘입니다.
임의의 노드 X에 연결 된 노드가 X-1, X+1, X*2 이고 가중치가 각각 1,1,0이라고 생각하면 됩니다.
다음의 그림처럼 2번 노드에 연결 된 노드는 2-1 = 1번, 2+1 = 3번, 2*2 = 4번 이고 각각 1,1,0의 가중치를 갖습니다.
그러면 다익스트라를 수행한 후 수빈이의 위치 N에서 동생의 위치 K로 가는 최소경로가 답이 됩니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstring>
#include <queue>
#define MAX 100001
using namespace std;
int subin, bro;
int cache[MAX];
struct Node
{
int idx, dist;
bool operator<(const Node &b) const
{
return idx > b.idx;
}
};
// 다익스트라 알고리즘
int getMinTime()
{
// cache 초기화
for (int i = 0; i < MAX; i++)
cache[i] = MAX;
cache[subin] = 0;
// 오름차순 우선순위 큐
priority_queue<Node> pq;
pq.push({subin, 0});
while (!pq.empty())
{
Node curr = pq.top();
int idx = curr.idx, dist = curr.dist;
pq.pop();
if (dist > cache[idx])
continue;
int nIdx, nDist;
// 2*x
nIdx = idx * 2, nDist = dist;
if (nIdx < MAX && nDist < cache[nIdx])
{
cache[nIdx] = nDist;
pq.push({nIdx, nDist});
}
// x-1
nIdx = idx - 1, nDist = dist + 1;
if (nIdx >= 0 && nDist < cache[nIdx])
{
cache[nIdx] = nDist;
pq.push({nIdx, nDist});
}
// x+1
nIdx = idx + 1, nDist = dist + 1;
if (nIdx < MAX && nDist < cache[nIdx])
{
cache[nIdx] = nDist;
pq.push({nIdx, nDist});
}
}
// 수빈 -> 동생까지의 최소경로 반환
return cache[bro];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> subin >> bro;
// 수빈이가 동생보다 앞에 있다면 -1로 밖에 이동할 수 없다
if (subin >= bro)
{
cout << subin - bro << '\n';
return 0;
}
cout << getMinTime();
return 0;
}
