[BFS] 백준 1697번 숨바꼭질(C++)

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

 

호호호호

뭔가

느낌이

..

DP느낌이 났어요

 

딱 문제 보자마자

[동적프로그래밍] 백준 1463번 1로 만들기(C++)

[동적프로그래밍] 백준 1463번 1로 만들기(C++)

어라..

1로 만들기랑 비슷한데

 

아예 이렇게 dp로 틀어서도 문제를 풀 수 있지만

 

BFS를 열렬히 풀고있는 내겐 BFS만 보였다고

 

휘비고

 

문제 자체는 이해했을 것이다

 

예제에 5 17의 경우

 

5 -> 4 -> 8 -> 16 -> 17 

이렇게 총 4번의 다리를 건너는 경우가 제일 빠르다

(이 4번 말고도 여러개 존재)

 

이걸 BFS로 어떻게 했냐면

살짝 DP를 이용했다

 

먼저 크게 3가지의 경우의 수가 존재한다

 

+1

-1

*2

 

이걸 어떻게 하냐고?
다 고려해보면 된다

 

queue에는, +1 -1 *2를 한 값을 넣어주고

그상태 그대로 dp[]값을 +1한채로 채워주면 된다.

이후 재방문하지 않게 visted를 사용하였다.

 

어라 그럼 어떻게 그게 최솟값인게 자명하죠? 란 생각이 들 수  있다.

사실 이 값이 최솟값이 아니게 되려면 

 

예를들어

 

1 6을 보자

dp[6]의 값을 구하면 되는 건데

이게

dp[5] 와 dp[7]과 d[3]에서 +1한 값중에 가장 최소가 되어야 하는게 아닌가?

근데 내가 하려는 식은 단순히 조건문도 없이 그저 바로 넣어주는 것인데

..

 

이런 고민을 한 내가 멍청했다

 

dp를 이용해서 값을 이미 집어넣고 난 후에는 , 그값은 최솟값인게 자명하다

 

예를들어 dp[6]의 값을 3*2를통해서 dp[3]+1로 넣었을 때 dp[5]+1보다 작을 가능성을 생각한게 아닌가?

 

그런 경우는 없다.

dp[]는 순서대로 채워지기 때문에, 만약 dp[5]+1이 dp[3]+1보다 작다면 당연히 dp[5]가 dp[3]보다 순서상 빨리 오는거다

 

예를들어

5 17을 보자

 

5 -> 10 -> 9 -> 18 -> 17의 순서로 갈때

 

5에서는 

4 6 10의 경우의수로

 

이후 4 6 10은

3,8,7,12,20,9

..

로 갈때 20이란 수의 dp값을 봐보자

20 dp는 dp[10]+1인데 19와 21이 있는가?

당연히 없다

 

뭐 아직도 살짝 헷갈리긴 하는데 자주자주 봐서 생각해보자

 

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

int arr[100001];

int dp[100001];

int d[2] = {-1, 1};

int n, m;

bool visited[100001];

void bfs(int temp);

int main()

{

    cin >> n >> m;

    dp[n] = 0;

    bfs(n);

    cout << dp[m] << "\n";

}

void bfs(int temp)

{

    visited[temp] = true;

    queue<int> q;

    q.push(temp);

    while (!q.empty())

    {

        int x = q.front();

        q.pop();

        for (int i = 0; i < 3; i++)

        {

            if (i == 2)

            {

                if (x * 2 < 100001 && !visited[x * 2])

                {

                    visited[x * 2] = true;

                    q.push(x * 2);

                    dp[x * 2] = dp[x] + 1;

                    // cout << x * 2 << " , " << dp[x * 2] << "\n";

                }

            }

            else if (x + d[i] < 100001 && x + d[i] >= 0 && !visited[x + d[i]])

            {

                visited[x + d[i]] = true;

                q.push(x + d[i]);

                dp[x + d[i]] = dp[x] + 1;

                // cout << x + d[i] << " , " << dp[x + d[i]] << "\n";

            }

            if (visited[m])

                return;

        }

        // cout << "par of : " << x << "\n";

    }

}

*2인경우와 + 1 - 1인경우를 따로 지정해 주었다

 

내용자체는 이해하기 쉬울것이라 생각한다.