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

 

 

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

 

진짜 넘 어려웠어

이모티콘 문제푼거처럼 할려했는데

 

#include <iostream>

#include <queue>

using namespace std;

int n, s;

bool visited[100001];

void bfs(int temp);

int main()

{

    cin >> n >> s;

    bfs(n);

}

void bfs(int temp)

{

    queue<pair<int, int>> q;

    q.push(make_pair(temp, 0));

    visited[temp] = true;

    while (!q.empty())

    {

        // 고려해야 하는건 위치와 시간

        int x = q.front().first;  // 위치

        int y = q.front().second; // 시간

        visited[x] = true;

        if (x == s)

        {

            cout << y << "\n";

            return;

        }

        q.pop();

        if (x + 1 < 100001 && !visited[x + 1])

            q.push(make_pair(x + 1, y + 1));

        if (x - 1 > 0 && !visited[x - 1])

            q.push(make_pair(x - 1, y + 1));

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

            q.push(make_pair(2 * x, y));

    }

}

이렇게 그냥 간단히 풀려했는데

 

저 저 저 저 저 2*x,y가 안됨

 

 

예를들어

 

4 6 이란 숫자가 들어오면

 

순서를 생각해보자

 

 

q에는

4이후

5,3,10이 들어올거고

 

5에서는 6

3에서는 2 6 이 들어올거잖아?

 

 

그럼 3->6가는건 비용이 0이니까 4->3가는 비용 1만 사용해서 1인데

4->6은 +1 +1 두번한거니까 비용이 2란말이야

 

그래서 3->6이 나오기 전에! 4->5->6이 먼저 순서상 나오게 되어서

이걸 우선적으로 처리하다보니 잘못된 답이 나오는거야

 

 

이거 풀려고 개고생했다

 

#include <iostream>

#include <queue>

using namespace std;

int n, s;

bool visited[100001];

void bfs(int temp);

int main()

{

    cin >> n >> s;

    if (n == s)

    {

        cout << 0 << "\n";

        return 0;

    }

    bfs(n);

}

void bfs(int temp)

{

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    q.push(make_pair(0, temp));

    visited[temp] = true;

    while (!q.empty())

    {

        // 고려해야 하는건 위치와 시간

        int y = q.top().first;  // 시간

        int x = q.top().second; // 위치

        visited[x] = true;

        if (x == s)

        {

            cout << y << "\n";

            return;

        }

        q.pop();

        if (x + 1 < 100001 && !visited[x + 1])

            q.push(make_pair(y + 1, x + 1));

        if (x - 1 >= 0 && !visited[x - 1])

            q.push(make_pair(y + 1, x - 1));

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

            q.push(make_pair(y, 2 * x));

    }

}

 

 

답은 요건데

이건 나도 인터넷으로찾았어

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

시간을 기준으로 우선순위 큐를 만들면 된다!

 

앞서 말한것은 순서상으로 뒤로 밀려나는 경우가 생겨서 그런건데

이 시간을 기준으로 순서를 정하면

 

 5 3 10 에서

6 이 q에들어가고

이후 2 6 이 q에 들어갈 때,

 

시간이 뒤에있는 6은 1이니까

이게 앞으로 뗑겨지는거

 

 

휴