방문한 노드에는 현재 노드에 도착할 때까지 걸리는 시간을 저장해주고, 다음에 방문할 때 저장된 값보다 걸린 시간이 적은 경우에만 값을 갱신, 계산하도록 했다.
알고리즘이 다익스트라로 구분되었기에 우선순위 큐도 써보았는데 정렬이 필요해서인지 시간도 메모리도 더 컸다.
코드 1 - 큐
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int visited[100001];
int Find(int start, int end) {
// 시작지점이 종료지점과 같다면 0 반환
if (start == end) return 0;
int now, sec, d[3] = { -1,1 }, min = 10000000;
queue <pair<int, int>> Q;
// init
Q.push({ start, 0 });
visited[start] = 0;
fill(visited, visited + 100001, min); // 최댓값으로 설정
while (!Q.empty()) {
now = Q.front().first, sec = Q.front().second;
Q.pop();
d[2] = now; // 3번째는 *2 이동
for (int i = 0; i < 3; i++) {
int next = now + d[i];
// 방문할 위치의 시간이 현재 방문할 때 걸리는 시간보다 적을 경우 방문할 필요 없음
// 이 줄 없어도 돌아가는 시간은 차이 없긴 한데 그래도 있는 게 시간을 좀 더 줄일 수는 있을 것 같음
if (next < 0 || next > 100000 || visited[next] <= sec) continue;
if (next == end) {
if (i != 2) min = min < sec + 1 ? min : sec + 1;
else min = min < sec ? min : sec;
visited[next] = min;
}
else {
if (i != 2) {
// 다음 방문할 노드까지 걸리는 시간이 min보다 크다면 큐에 저장 X
if (sec + 1 < min) Q.push({ next, sec + 1 });
visited[next] = sec + 1;
}
else {
Q.push({ next, sec });
visited[next] = sec;
}
}
}
}
return min;
}
int main() {
int N, K;
scanf("%d %d", &N, &K);
printf("%d", Find(N, K));
return 0;
}
코드 2 -우선순위 큐
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int visited[100001];
int Find(int start, int end) {
// 시작지점이 종료지점과 같다면 0 반환
if (start == end) return 0;
int now, sec, d[3] = { -1,1 }, min = 10000000;
priority_queue <pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>>> Q;
// init
Q.push({ 0,start }); visited[start] = 0;
fill(visited, visited + 100001, min); // 최댓값으로 설정
while (!Q.empty()) {
now = Q.top().second, sec = Q.top().first;
Q.pop();
// 우선순위 큐이므로 sec가 큰 게 한 번 나온 이후로는 모든 sec > min
// 코드 1과 이 부분만 다름
if (sec >= min) break;
d[2] = now; // 3번째는 *2 이동
for (int i = 0; i < 3; i++) {
int next = now + d[i];
// 방문할 위치의 시간이 현재 방문할 때 걸리는 시간보다 적을 경우 방문할 필요 없음
if (next < 0 || next > 100000 || visited[next] <= sec) continue;
if (next == end) {
if (i != 2) min = min < sec + 1 ? min : sec + 1;
else min = min < sec ? min : sec;
visited[next] = min;
}
else {
if (i != 2) {
// 다음 방문할 노드까지 걸리는 시간이 min보다 크다면 큐에 저장 X
if (sec + 1 < min) Q.push({ sec + 1, next });
visited[next] = sec + 1;
}
else {
Q.push({ sec, next });
visited[next] = sec;
}
}
}
}
return min;
}
int main() {
int N, K;
scanf("%d %d", &N, &K);
printf("%d", Find(N, K));
return 0;
}
