백준 1697 숨바꼭질 - bfs - c++

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

1697번: 숨바꼭질

한 7번;; 만에 풀었다.

큐에다가 bfs를 진행하면서 넣고 빼고를 반복하면서 카운팅만 잘 해주면 풀 수 있는 문제지만

따져야 되는 조건들을 안따질 시 런타임 에러가 난다.

 

조심해야 할점 -

• queue에서 push는 뒤에서 이뤄지고, pop은 앞에 거에서 이뤄진다.
• 처음에는 bool visited[100002]를 사용하지 않고 풀었는데, 이렇게 될시에는 방문했던 노드도 큐에 다시 넣어진다. 이렇게 될 시에는 O(3**n) 의 시간복잡도로 코드가 돌아가서 메모리 초과가 발생 할 수 있다.
• 각각 큐에 push를 할때 if 조건을 잘 따져봐야 한다. 3가지 경우 모두다. 본인은  item +1<=100000 조건을 생각 못하고 풀어서 계속 틀렸었다.

이러한 조건들을 반드시 풀면서 생각해보도록 하자 ㅜㅜ

 

#include <iostream>
#include <queue>
using namespace std;
int result=0;
int n,k;
bool visited[100002];
 
void bfs(int current){
    queue<int> dq;
    dq.push(current);
    visited[current]=true;
    while(!dq.empty()){
        int size = dq.size();
        for(int i=0; i<size; i++){
            int item = dq.front();
//            cout<<item<<"\n";
            dq.pop();
            if(item==k)
                return;
            else{
                if(item +1<=100000) {
                    if (!visited[item + 1]) {
                        dq.push(item + 1);
                        visited[item + 1] = true;
                    }
                }
                if (item - 1 >= 0) {
                    if(!visited[item-1]) {
                        dq.push(item - 1);
                        visited[item-1]=true;
                    }
                }
                if(2*item<=100000) {
                    if (!visited[2 * item]) {
                        dq.push(2 * item);
                        visited[2 * item] = true;
                    }
                }
            }
        }
        result++;
    }
}
 
int main(void){
    cin>>n>>k;
    bfs(n);
    cout<<result;
}