[BOJ/C++] 숨바꼭질 3(13594번)

1. 개요

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

1-1. 설명

앞선 문제 숨바꼭질과 동일하게 수빈이는 동생을 찾을 수 있는 가장 빠른 시간을 구하는 것이다. 달라진 점은 순간이동 할 때 시간이 들지 않는다는 것이다. 

1-2. 제한 사항

 - 첫 줄에 수빈이 위치 N, 동생 위치 K가 주어짐

---

2. 구현

2-1. 풀이

처음에는 앞전에 풀었던 BFS에 조건을 더 추가하면 문제가 풀릴 것이라 생각하여 BFS로 구현해냈다. 여기서, 최단시간을 구하는 것이므로 다익스트라로도 풀수있다는 것을 보고 추가적으로 다익스트라로도 풀어보았다. 코드가 그렇게 달라진 점이 크게 없어 맞는진 모르겠지만, 이런식으로 구현해내니 두 코드 다 정상작동 되었다. 

2-2. 코드

 - BFS

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 100001;
constexpr size_t INF = 99999999;
int visited[MAX_NUM];
int queue[MAX_NUM];
void BFS(int start, int end);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;
    fill(visited, visited + MAX_NUM + 1, INF);
    BFS(N, K);
    cout << visited[K];
    return 0;
}

void BFS(int start, int end) {
    int front = -1, rear = -1;
    queue[++rear] = start;
    visited[start] = 0; // INF로 초기화 해주었으므로, 시작값은 0으로 초기화해주어야 함
    
    while (front != rear) {
        int cur = queue[++front];
        if (cur == end) break;
        
        // 계산한 visited와 다음 노드의 visited를 비교하는 부분 조건문에 추가
        if (cur - 1 >= 0 && visited[cur - 1] > visited[cur] + 1) { 
            visited[cur - 1] = visited[cur] + 1;
            queue[++rear] = cur - 1;
        }
        if (cur + 1 <= MAX_NUM && visited[cur + 1] > visited[cur] + 1) {
            visited[cur + 1] = visited[cur] + 1;
            queue[++rear] = cur + 1;
        }
        if (cur * 2 >= 0 && cur * 2 <= MAX_NUM && visited[cur * 2] > visited[cur]) {
            visited[cur * 2] = visited[cur];
            queue[++rear] = cur * 2;
        }
    }
}

 - dijkstra

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 100001;
constexpr size_t INF = 99999999;
int dist[MAX_NUM];
void dijkstra(int start, int end);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;
    fill(dist, dist + MAX_NUM + 1, INF);
    dijkstra(N, K);
    cout << dist[K];
    return 0;
}

void dijkstra(int start, int end) {
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
    queue.push({ 0, start });

    while (!queue.empty()) {
        int cost = queue.top().first;
        int node = queue.top().second;
        queue.pop();

        if (node - 1 >= 0 && dist[node - 1] > dist[node] + 1) {
            dist[node - 1] = dist[node] + 1;
            queue.push({ cost + 1, node - 1 });
        }

        if (node + 1 <= MAX_NUM && dist[node + 1] > dist[node] + 1) {
            dist[node + 1] = dist[node] + 1;
            queue.push({ cost + 1, node + 1 });
        }

        if (node * 2 >= 0 && node * 2 <= MAX_NUM && dist[node * 2] > dist[node]) {
            dist[node * 2] = dist[node];
            queue.push({ cost, node * 2 });
        }
    }
}