최단거리 구하는 BFS (숨바꼭질)

BFS는 모든 가중치가 1일때, 최단거리를 구하는 알고리즘 

1. 최소 비용 문제여야 한다

2. 간선의 가중치가 1이어야 한다.

3. 정점과 간선의 개수가 적어야한다. (5백만개 정도까지)

 

간선의 가중치가 문제에서 구하라고 하는 최소 비용과

의미가 일치해야 한다!

거리의 최소값 구하는 문제라면 가중치는 거리

시간의 최소값 구하는 문제라면 가중치는 시간

 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

시간의 최소값 -> 가중치가 시간 '1초'. BFS 쓰자

#include <iostream>
#include <queue>
 
using namespace std;
const int MAX = 200000;
bool check[MAX + 1];
int dist[MAX + 1];
 
int main()
{
    int n, m;
    cin >> n >> m;
    check[n] = true;
    dist[n] = 0;
    queue<int> q;
    q.push(n);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        if (now - 1 >= 0)
        {
            if (check[now - 1] == false)
            {
                q.push(now - 1);
                check[now - 1] = true;
                dist[now - 1] = dist[now] + 1;
            }
        }
 
        if (now + 1 < MAX)
        {
            if (check[now + 1] == false)
            {
                q.push(now + 1);
                check[now + 1] = true;
                dist[now + 1] = dist[now] + 1;
            }
        }
 
        if (2 * now < MAX)
        {
            if (check[2 * now] == false)
            {
                q.push(2 * now);
                check[2 * now] = true;
                dist[2 * now] = dist[now] + 1;
            }
        }
    }
 
    cout << dist[m] << '\n';
}

 stack<int> ans;
    for (int i=m; i!=n; i=from[i]) {
        ans.push(i);
    }
    ans.push(n);
    while (!ans.empty()) {
        cout << ans.top() << ' ';
        ans.pop();
    }