(BOJ) 1697 풀이

1697

#include<bits/stdc++.h>
using namespace std;
int visited[100002];
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    queue<int> Q;
    fill(visited,visited+100002,-1);
    int N,K;
    cin >> N >> K;
    Q.push(N);
    visited[N]=0;
    while(visited[K]==-1){
        int cur=Q.front();
        Q.pop();
        for(int nxt:{cur-1,cur+1, cur*2}){
            if(nxt<0 || nxt >100000 || visited[nxt]!=-1)continue;
            Q.push(nxt);
            visited[nxt]=visited[cur]+1;
        }
    }
    cout << visited[K] << '\n';
}

동생은 가만히 있으므로, X+1, X-1, X*2 이 3개를 큐에 넣으면서 visited 에 초를 1씩 증가시키다가 목적지에 최초로 도달하면 그 때 값을 출력해준다.

먼저 pair 으로 좌표랑 초를 같이 넣을려 했는데, 메모리초과가 나서 배열로 바꿧당

visited[nxt]≠-1 을 안넣어줘서 메모리초과가 난 걸 수도 있다.