1697 숨바꼭질.

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

1697번: 숨바꼭질

 

문제를 처음 봤을때 3가지 +1, -1, *2 를 다 보면서 deque에 집어넣고 계산한 결과를 

사실 여기서 제대로 로직을 발견하지 못하여서 

처음에는 3개마다 재귀를 돌았기 때문에 로직상 오류가 발생했고 이를 해결 하고자 하였으며 이것이 곳 bfs의 처리 방식이라는 것을

확인 할 수 있었다.

하나씩 찾아보면서 정답을 발견하면 리턴하게 했다. 처음 맥시멈으로 가지고 있는 길이가 100000만 까지 였기 때문에

넉넉하게 잡아서 1000001보다 큰 값을 처리하고, 사실 처음 올바른 값을 찾으면 그값이 정답이 될 것 이기 때문에 

dq를 전달해서 처리하도록 구현하였다.

 

#include <iostream>
#include <queue>

using namespace std;

char check[1000001];

int solve(deque<int>& dq,  int m, int cnt) {
    int len;
    int value;

    len = dq.size();
    for (int i = 0; i < len; ++i) {
        value = dq[0];
        if (value > 0 && check[value - 1] == 0)
            dq.push_back(value - 1);
        if (value < 100000 && check[value + 1] == 0)
            dq.push_back(value + 1);
        if (value <= 50000 && check[value * 2] == 0)
            dq.push_back(value * 2);
        dq.pop_front();
        check[value] = 1;
    }
    for (int i = 0; i < dq.size(); ++i) {
        if (dq[i] >= 0 && dq[i] <= 1000000)
        {
            check[dq[i]] = 1;
            if (dq[i] == m)
                return (cnt);
        }
    }
    return (solve(dq, m, cnt + 1));
}