문제

최단 경로를 찾는 문제로, 이동할 수 있는 방법이 i-1, i+1, 2*i인 경우

Idea

N에서 출발해 K로 도착하는 최단 경로를 BFS를 이용해 찾는다.

단, N과 K가 동일한 경우 BFS 이전에 return한다.

방문한 곳은 visit에 집어넣는데, vector<bool>에 방문했다면 true로 바꾼다. 여담으로 처음에는 방문한 곳을 vector<int>에 push_back 한 다음 std::find로 찾아줬는데, 이는 시간 초과를 리턴했어서 그냥 vector<bool>에 집어넣었다.

Code

// link: https://www.acmicpc.net/problem/1697

#include <iostream>
#include <vector>
#include <queue>

constexpr int MAX_POSITION = 100000;

typedef struct{
    int i;
    int time;
} pos;

int findSister(const int N, const int K){
    //check N == K
    if (N==K){
        return 0;
    }

    //make visit
    std::vector<bool> visit(MAX_POSITION, false);
    visit[N] = true;

    //BFS
    std::queue<pos> q;
    q.push({N, 0});

    while (!q.empty())
    {
        const pos current = q.front();
        q.pop();

        const int i = current.i;
        const int time = current.time;

        for (const auto i_new : {i-1, i+1, 2*i}){
            if (i_new == K){
                //arrive
                //  -> return time+1

                return time+1;               
            }

            if ((i_new < 0) || (i_new>MAX_POSITION)){
                //out of map

                continue;
            }
            else if (visit[i_new]){
                //visit already

                continue;
            }
            else{
                //not visit
                
                q.push({i_new, time+1});
                visit[i_new] = true;
            }
        }
    }
    
    return -1;
}

int main(){
    int N = 0;
    std::cin >> N;
    
    int K = 0;
    std::cin >> K;

    std::cout << findSister(N, K) << std::endl;

    return 0;
}
'''