본문 바로가기
알고리즘

[알고리즘] c++ cpp 숨바꼭질 시리즈 (숨바꼭질3)

by keel_im 2020. 10. 4.
반응형

포인트

1. bfs() 를 잘 알고 있는가?

2. bfs는 모든 노드를 지날때 같은 가중치를 같는 노드만 탐색을 할 수 있다. 이에 dequeue 를 사용을 하여 가중치를 다르게 처리를 하여 bfs 를 진행할 수 있도록 한다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <deque>
#include <cstring>

using namespace std;

int n, m;
int dist[100001];

void bfs() { // bfs 는 모든 노드로 가는 가중치가 1인 경우나 같은 경우이다.
    // 지금 문제는 하나의 가중치가 다름으로 다르게 처리를 해야 한다.
    deque<int> q;
    q.push_back(n);
    dist[n] = 0;

    while (!q.empty()) {
        int x = q.front(); // 가중치가 0이기 때문에 앞으로 꺼낸다.
        q.pop_front();

        if (x == m) {
            cout << dist[m] << '\n';
            return;
        }
        if (2 * x < 100001 && dist[2 * x] == -1) { // 가중치 0
            q.push_front(2 * x);
            dist[2 * x] = dist[x];
        }

        if (x - 1 >= 0 && dist[x - 1] == -1) { // 가중치 1
            q.push_back(x - 1);
            dist[x - 1] = dist[x] + 1;
        }

        if (x + 1 < 100001 && dist[x + 1] == -1) { //가중치 1
            q.push_back(x + 1);
            dist[x + 1] = dist[x] + 1;
        }
    }
}

int main() {
    cin >> n >> m;
    memset(dist, -1, sizeof(dist));
    bfs();

    return 0;
}
반응형

댓글