13549: 숨바꼭질 3

• toc {:toc}

문제 확인하기

풀이

메모리 초과

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
 
const int MAX = 100005;
int vis[MAX];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, K, res=MAX, nx, ny;
    queue<int> q;
    
    cin >> N >> K;
 
    if(N == K) {
        cout << 0 << '\n';
        exit(0);
    }
    vector<int> vec;
    vis[N] = 1;
    q.push(N);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int next : {cur-1, cur+1, cur*2}){
            if(0 <= next && next <= MAX){
                if(vis[next] >= 1 && next != K) continue;
                q.push(next);
                if((cur*2)==next) vis[next] = vis[cur];
                else vis[next] = vis[cur]+1;
 
                if(next == K){
                    vec.push_back(vis[next]);
                }
            }
        }
    }
 
    for(int i = 0; i < vec.size(); i++){
        if(res > vec[i]) res = vec[i];
    }
 
    cout << res-1 << '\n';
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100001;
int vis[MAX];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, K, res=MAX;
    queue<int> q;
    
    cin >> N >> K;
 
    fill(vis, vis+MAX, MAX);
    vis[N] = 0;
    q.push(N);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        if (cur == K){
            res = vis[cur];
            break;
        }
 
        if(cur * 2 < MAX && vis[cur * 2] > vis[cur]){
            vis[cur*2] = vis[cur];
            q.push(cur*2);
        }
 
        if(cur + 1 < MAX && vis[cur + 1] > vis[cur] + 1){
            vis[cur+1] = vis[cur] + 1;
            q.push(cur+1);
        }
 
        if(cur - 1 >= 0 && vis[cur - 1] > vis[cur] + 1){
            vis[cur - 1] = vis[cur] + 1;
            q.push(cur - 1);
        }
    }
 
 
    cout << res << '\n';
 
 
    return 0;
}