1697번 숨바꼭질 | BFS | Baekjoon BOJ 백준 1697 C++ 코드, 해설, 풀이

 

 

 

이번 포스팅은 백준 1697번 숨바꼭질입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

기본 알고리즘

최단 경로(시간) = BFS (너비 우선 탐색)

 

참고

 

 

 

전체 코드

 

//백준1697 숨바꼭질
 
#include <iostream>
#include <queue>
using namespace std;
 
const int MAX = 100001;
int N, K;
bool visited[MAX] = { 0, };
int path[MAX];
queue<int> q;
 
void printPath() {
    cout << "[PATH]" << endl;
    for (int i = N; i <= K; i++) {
        printf("%2d ", i);
    }
    printf("\n");
    for (int i = N; i <= K; i++) {
        printf("%2d ", path[i]);
    }
    printf("\n");
}
 
void BFS(int v) {
    path[v] = 0;
    visited[v] = true;
    q.push(v);
 
    while (!q.empty()) {
        int w = q.front();
        if (w == K) break;
        q.pop();
 
        if (visited[w + 1] == 0 && w + 1 >= 0 && w + 1 < MAX) {
            visited[w + 1] = true;
            q.push(w + 1);
            path[w + 1] = path[w] + 1;
        }
        if (visited[w - 1] == 0 && w - 1 >= 0 && w - 1 < MAX) {
            visited[w - 1] = true;
            q.push(w - 1);
            path[w - 1] = path[w] + 1;
        }
        if (visited[w * 2] == 0 && w * 2 >= 0 && w * 2 < MAX) {
            visited[w * 2] = true;
            q.push(w * 2);
            path[w * 2] = path[w] + 1;
        }
    }
 
}
 
int main() {
    cin >> N >> K;
 
    BFS(N);
 
    //printPath();
    cout << path[K];
}