[C++] 13549번 숨바꼭질 3 - 0-1 BFS

#include <iostream>
#include <deque>
#include <vector>

#define MAX_LOC 200003

using namespace std;

int N, K;  //수빈이의 위치, 동생의 위치
vector<int> c(MAX_LOC);  //이미 탐색했는지 확인
deque<int> q;  //갈 예정인 경로 저장

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    
    q.push_back(N); c[N]=1;
    while(!q.empty()) {
        int n=q.front(); q.pop_front();  //앞에 있는게 우선
        
        if(n==K)
            break;
        if(2*n<MAX_LOC && !c[n*2]) {
            q.push_front(n*2);
            c[n*2]=c[n];
        }
        if(n+1<MAX_LOC && !c[n+1]) {
            q.push_back(n+1);
            c[n+1]=c[n]+1;
        }
        if(n>0 && !c[n-1]) {
            q.push_back(n-1);
            c[n-1]=c[n]+1;
        }
    }
    cout << c[K]-1;
    
    return 0;
    
}

 

 

0-1 BFS라는 새로운 알고리즘을 공부해야 했다. 0-1 BFS가 왜  작동하는 것인지 잘 이해가 되지 않았는데 생각해보니까 약간 그리드 알고리즘이 생각나는 알고리즘이었다. 아무튼 디큐를 이용해서 풀 수 있었고 왜 항상 답에 +1이 나오는거야! 하고 고민 많이 했었는데 생각해보니 맨 처음에 1을 넣어주고 시작해더랬지 ㅋㅋㅋ

 

 

 

<C++ 덱-deque>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=shinsy11&logNo=220586163805 

C++ STL 프로그래밍: 덱(deque)

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.