[백준] 17071 숨바꼭질 5

 

BFS를 이용하는 문제다!! 최적화문제!!

먼저 규칙을 찾기위해 층이 있는 트리라고 생각해보자

그럼 홀수,짝수 깊이에 갈 수 있는 곳들이 계산된다

근데 이 때 중요한 규칙이 발견된다

 

내가 홀수에서 방문한 곳은 다음 홀수에도 갈수있고 짝수도 마찬가지다!

이걸 발견했으면 BFS로 check배열을 check[size][2]로 잡고 홀짝에 방문하는지 확인하면 된다

 

나는 발견하고 참 어렵게 생각하고 계속 틀렸다

홀 짝에 반복되는 성질로 줄이지 못하고 구간이라고 생각했다

현재깊이 -2 층에서 간건 현재도 방문 할 수 있기 때문에 구간이 넓어지는걸로 풀려다가 망해따

 

+1, -1이 반복 된다는건 갔다가 왔다가 하므로 홀짝의 성질을 이용해야하는데 최적화의길이란..

이런걸 생각 못하면 계속 틀리는문제는 매번 틀릴거같다...!

 

하나 배워간당~~! 비슷한 문제 사실 많이 풀어봤는데 못 떠올리는게 슬프다...

 

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int SIZE = 5e5+5;
int n,k;
bool check[SIZE][2];
 
int main(){
    scanf(" %d %d",&n,&k);
    if(n==k) puts("0");
    else{    
        queue<int> q;
        q.push(n);
        check[n][0]=true;
        int ans=1;
        
        while(int s = q.size()){
            k+=ans;
            if(k>500000) break;
            while(s--){
                int now = q.front();
                q.pop();
                for(int i=0;i<3;i++){
                    int next = now;
                    if(i==0) next-=1;
                    else if(i==1) next+=1;
                    else next*=2;
                    if(0<=next && next<=500000 && !check[next][ans%2]){
                        check[next][ans%2]=true; q.push(next);
                    }
                }
            }
            if(check[k][ans%2]) {
                printf("%d\n",ans); return 0;
            }
            ans+=1;
        }
        puts("-1");
    }
}