[백준] 1697번 숨바꼭질

 

 

문제

 

소스코드

 

#include<iostream>
#include<queue>
#include<utility>
constexpr int MAX_ARRAY_SIZE = 100001;
constexpr int MAX_WEIGHT = 500000;
 
using pairData = std::pair<int, int>; //index, weight
 
int g_weight[MAX_ARRAY_SIZE];
 
void Search(int N, int K) {
 
    //N과 K가 같은경우
    if (N == K) {
        std::cout << "0\n";
        return;
    }
 
    for (int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        g_weight[i] = MAX_WEIGHT;
    }
 
    std::priority_queue<pairData, std::vector<pairData>, std::greater<>>pq;
    pq.emplace(pairData{ N,0 });
 
    while (pq.empty() == false) {
        auto topValue = pq.top();
        pq.pop();
 
        //더하기
        if ((topValue.first + 1 < MAX_ARRAY_SIZE) &&
            (g_weight[topValue.first + 1] > topValue.second + 1)) {
            g_weight[topValue.first + 1] = topValue.second + 1;
            pq.emplace(pairData{ topValue.first + 1,topValue.second + 1 });
        }
        //빼기
        if ((topValue.first - 1 >= 0) && 
            (g_weight[topValue.first - 1] > topValue.second + 1)) {
            g_weight[topValue.first - 1] = topValue.second + 1;
            pq.emplace(pairData{ topValue.first - 1,topValue.second + 1 });
        }
        //곱하기
        if ((topValue.first * 2 < MAX_ARRAY_SIZE) && 
            (g_weight[topValue.first * 2] > topValue.second + 1)) {
            g_weight[topValue.first * 2] = topValue.second + 1;
            pq.emplace(pairData{ topValue.first * 2,topValue.second + 1 });
        }
    }
    std::cout << g_weight[K] << "\n";
}
 
int main() {
    int N, K; //수빈, 동생
    std::cin >> N >> K;
    Search(N, K);
}

 

 

후기

이 문제를 해결하기 위한 키워드는 BFS 혹은 다익스트라이다.

 

이 문제는 수빈이가 동생을 찾으러 가는 최단 시간 타임을 찾아서 출력하는 문제이다.

 

BFS로 풀어도 충분히 통과가 가능하고 나는 다익스트라 알고리즘을 사용해서 최단 경로를 찾아서 문제를 풀었다. 

 

중간에 틀리는 경우가 있었는데 MAX_WEIGHT 값이나 배열의 최대 INDEX 값이 작아서 오류가 발생했다 이러한 사소한 문제가 의외로 못 찾으면 시간이 꽤 걸리는 거 같다.

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/1697

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 다익스트라 알고리즘(Dijkstra algorithm)

[온라인 코딩/탐색(Search)] - [백준] 1753번 최단경로

[온라인 코딩/탐색(Search)] - [구름 IDE] 다익스트라 알고리즘(Dijkstra's Algorithm)(★4)