백준 1697 : 숨바꼭질

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

1697번: 숨바꼭질

 

#include <iostream>
#include <algorithm>
#include <queue>
 
typedef int sec;
typedef int pos;
 
int N, K;
int minimumSec = 987654321;
 
int visited[200001];
 
struct state
{
    int pos;
    int sec;
};
 
void input()
{
    std::cin >> N >> K;
}
 
void solve()
{
    if (N == K)
    {
        minimumSec = 0;
        return;
    }
    std::queue<state> bfs;
    int dest = K;
 
    bfs.push({ N, 0 });
    while (bfs.empty() == false)
    {
        state curr = bfs.front();
        visited[curr.pos] = 1;
        bfs.pop();
 
        if (curr.pos > dest)
        {
            int restSec = curr.sec + curr.pos - dest;
            minimumSec = minimumSec > restSec ? restSec : minimumSec;
            continue;
        }
        if (curr.sec > dest - N)
        {
            minimumSec = minimumSec > curr.sec ? curr.sec : minimumSec;
            return;
        }
 
        if (dest == curr.pos * 2 || dest == curr.pos + 1 || dest == curr.pos - 1)
        {
            minimumSec = minimumSec > curr.sec + 1 ? curr.sec + 1 : minimumSec;
            return;
        }
        else
        {
            if (visited[curr.pos * 2] == 0)
            {
                bfs.push({ curr.pos * 2, curr.sec + 1 });
            }
            if (visited[curr.pos + 1] == 0)
            {
                bfs.push({ curr.pos + 1, curr.sec + 1 });
            }
            if (curr.pos > 0)
            {
                if (visited[curr.pos - 1] == 0)
                {
                    bfs.push({ curr.pos - 1, curr.sec + 1 });
                }
            }
        }
    }
}
 
void solve_dp()
{
}
 
void output()
{
    std::cout << minimumSec;
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}

 

BFS의 뭐 개념이야 그렇다 쳐도

 

핵심은 이미 접근한 곳에 대해 어떻게 배제하는가

 

visited 변수를 안쓰고 하려면 어떤 방식이 필요할까...