BOJ 12851 : 숨바꼭질 2 [C++]

 

12851번: 숨바꼭질 2

 

 

처음 문제를 읽고 BFS를 떠올리긴 했는데,

뭔가 방문을 처리하는 배열을 boolean으로 만든다면 모든 경우의 수를 찾을 수 없다고 생각했다.

'조건문으로만 처리해서 할 수 있지 않을까?'라고 생각했다가 각 지점에 도달하는 최소 시간을 기록하기로 했다.

 

고려한 조건들

• 현재까지 이동한 시간이 '목적지(k)까지의 최소시간'보다 크면 continue
• '각 지점에 도달하는 최소 시간'보다 큰 시간에 도달하면 그다음은 고려하지 않고 continue
• X + 1, 2 * X의 경우 n < k인 경우에만 고려
• X - 1의 경우 n < k이면서 현재 위치가 (n / 2) - 1보다 작다면 그다음은 고려하지 않고 continue

 

통과 후 다른 블로그 글 들을 보면서 boolean으로 방문 처리를 해도 된 다는 것을 이해했다.

다만 큐에서 pop한 후 처리해주어야 한다는 것이 달랐다.

 

내가 한 방식도, boolean으로 방문처리를 하는 방식도 모두 되는 이유는

bfs로 어떤 지점에 최초로 도달하면, 그때가 최소비용이기 때문이라고 이해했다.

 

추가로 n == k 일 경우에는 0 1을 출력하면 된다.

 

비용으로 방문처리 한 코드

#include <iostream>
#include <queue>

int min_time = 100001;
int number_of_routes = 0;
int dp[100001];

void bfs(int n, int k) {
    std::queue<std::pair<int, int>> record;
    record.push({n, 0});
    dp[n] = 0;

    while (!record.empty()) {
        int cur_record = record.front().first;
        int cur_time = record.front().second;
        record.pop();

        if (cur_record == k) {
            min_time = cur_time;
            number_of_routes++;
            continue;
        }

        if (cur_time > min_time) {
            continue;
        }

        if (cur_record + 1 < 100001 && n < k) {
            if (cur_time + 1 <= dp[cur_record + 1]) {
                dp[cur_record + 1] = cur_time + 1;
                record.push({cur_record + 1, cur_time + 1});
            }
        }

        if (cur_record - 1 > -1) {
            if (n < k && cur_record - 1 < n / 2 - 1) {
                continue;
            }
            if (cur_time + 1 <= dp[cur_record - 1]) {
                dp[cur_record - 1] = cur_time + 1;
                record.push({cur_record - 1, cur_time + 1});
            }
        }

        if (cur_record * 2 < 100001 && n < k) {
            if (cur_time + 1 <= dp[cur_record * 2]) {
                dp[cur_record * 2] = cur_time + 1;
                record.push({cur_record * 2, cur_time + 1});
            }
        }
    }
}

int main() {
    for (int i = 0; i < 100001; i++) {
        dp[i] = 100001;
    }

    int n = 0, k = 0;
    std::cin >> n >> k;

    if (n == k) {
        std::cout << "0\n1\n";
    } else {
        bfs(n, k);
        std::cout << min_time << "\n" << number_of_routes << "\n";
    }

    return 0;
}

 

 

boolean으로 방문처리 한 코드

#include <iostream>
#include <queue>

int min_time = 100001;
int number_of_routes = 0;
bool visited[100001];

void bfs(int n, int k) {
    std::queue<std::pair<int, int>> record;
    record.push({n, 0});
    visited[n] = true;

    while (!record.empty()) {
        int cur_record = record.front().first;
        int cur_time = record.front().second;
        record.pop();
        visited[cur_record] = true;
        
        if (cur_time > min_time) {
            continue;
        }

        if (cur_record == k) {
            min_time = cur_time;
            number_of_routes++;
            continue;
        }


        if (cur_record + 1 < 100001 && n < k && !visited[cur_record + 1]) {
            record.push({cur_record + 1, cur_time + 1});
        }

        if (cur_record - 1 > -1 && !visited[cur_record - 1]) {
            if (n < k && cur_record - 1 < n / 2 - 1) {
                continue;
            }
            record.push({cur_record - 1, cur_time + 1});
        }

        if (cur_record * 2 < 100001 && n < k && !visited[cur_record * 2]) {
            record.push({cur_record * 2, cur_time + 1});
        }
    }
}

int main() {
    for (int i = 0; i < 100001; i++) {
        visited[i] = false;
    }

    int n = 0, k = 0;
    std::cin >> n >> k;

    if (n == k) {
        std::cout << "0\n1\n";
    } else {
        bfs(n, k);
        std::cout << min_time << "\n" << number_of_routes << "\n";
    }

    return 0;
}