Beakjoon 1697 숨바꼭질

07 Mar 2021 in Algorithm

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

나의 풀이

기본적으로 BFS로 탐색을 하면서 방문할 때 추가적으로 깊이를 저장해준다.
BFS로 탐색을 하기 때문에 K에 가장 먼저 도착하는 경우는 깊이가 가장 낮은 경우이고, 이는 수빈이가 동생을 찾는 가장 빠른 시간이다.

풀이 코드 : 1697 숨바꼭질

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

using namespace std;

int visit[100001] = {0,};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin>>N>>K;

    int start = N;
    visit[start] = 1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        if(curr == K) break;
        if(curr+1 <= 100000 && curr < K && visit[curr+1] == 0){
            visit[curr+1] = visit[curr] + 1;
            q.push(curr+1);
        }
        if(curr-1 >= 0 && visit[curr-1] == 0){
            visit[curr-1] = visit[curr] + 1;
            q.push(curr-1);
        }
        if(curr*2 <= 100000 && curr < K && visit[curr*2] == 0){
            visit[curr*2] = visit[curr] + 1;
            q.push(curr*2);
        }

    }

    cout<<visit[K] - 1;

}

채점결과