[백준] 13549번: 숨바꼭질 3 (C++)

 

BFS로 해결할 수 있는 문제

그리디 알고리즘과 유사하게 풀 수 있는 문제다

 

0초 동안은 2배로 이동할 수 있으므로

먼저 2배 이동이 가능한지 여부를 판단한다

이후 한 칸 전진할지 후진할지를 판단한다

 

이후 min_ 값을 통해 최소 시간을 구한다

 

함수가 많이 쓰이진 않지만

꽤 복잡하게 구성되어 있는 문제인 듯하다

 

// baekjoon 13549

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

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int arr[100001];
//bool visited[101][101][101] ;

//int dir[6][3] ;

int N, K;
queue<int> q;

int min_ = 100000;

// BFS
void bfs(){
    q.push(N);
    arr[N] = 0;
    
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        
        if(current == K){
            min_ = arr[current];
            return;
        }
        
        if(current * 2 < 100001 && arr[current * 2] > arr[current]){
            arr[current * 2] = arr[current];
            q.push(current * 2);
        }
        
        if(current + 1 <100001 && arr[current + 1] > arr[current] + 1){
            arr[current + 1] = arr[current] + 1;
            q.push(current + 1);
        }
        if(current - 1 >= 0 && arr[current - 1] > arr[current] + 1){
            arr[current - 1] = arr[current] + 1;
            q.push(current - 1);
        }
    }
}


// 배열, 방문여부, 큐 초기화
/*
void reset(){
}
*/

int main(){
    init();
    
    cin >> N >> K;
    
    for(int i = 0; i < 100001; i++){
        arr[i] = 100000;
    }
    
    bfs();
    
    cout << min_;
    return 0;
}

 

참고사이트

[백준] 13549번 : 숨바꼭질 3 C++ 풀이 (tistory.com)