[Baekjoon/C++] 1697번 숨바꼭질

문제 설명

problem_ex

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BFS(int n, int k){
    queue<pair<int, int>> q;
    vector<bool> visited(100001, false); 

    q.emplace(n, 0);
    visited[n]=true;

    while(!q.empty()){
        int x = q.front().first;
        int sec = q.front().second;
        q.pop();

        if(x==k){
            cout << sec << "\n";
            break;
        }

        int next[3]={x-1, x+1, 2*x};

        for(int i=0; i<3; i++){
            if(!visited[next[i]] && next[i]>=0 && next[i]<100001){
                q.emplace(next[i], sec+1);
                visited[next[i]]=true;  
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin >> N >> K;

    BFS(N, K);

    return 0;
}

visited 배열 선언을 통해 방문 여부를 체크하는 이유!

먼저 방문한 경로가 항상 더 짧기 때문에, 이미 더 짧은 경로로 방문한 위치를 나중에 더 긴 경로로 다시 방문하게 되면 최단 경로를 보장할 수 없게 되고 중복된 경로로 인한 불필요한 연산과 메모리가 낭비된다.

처음 방문 여부를 체크하지 않고 제출했더니 메모리 초과가났다.
visited 배열로 체크 후 다시 제출했더니 메모리 초과가 해결되었다.

yoon0722

문제 설명

코드 구현