BOJ 1697 - 숨바꼭질 (C++)

오늘의 깨달음 : CHATGPT는 신이다....

일단 어떻게 접근해야 되지? 되게 고민함
dp....라기에는 k 뒤에 있는 값에서 넘어오는 것도 정답이 될 수 있으니까 탐색을 멈추는 지점을 못찾겠다... 싶었고
브루트포스는 원래 잘 못 함. (?) ㅋㅋㅋㅋㅋ 그래서 풀이가 도저히 안 써졌음... 이건 걍 내가 연습을 해야겠고

그래서 결국 무슨 풀이 썼는지 봤는데 bfs더라. 그래서 바로 따라함ㅋㅋㅋㅋ

답을 내는 건 쉬웠다. 근데 대체 무슨 이유인지 자꾸 메모리 초과가 떴다.
첫 번째 이유는 찾기 쉬웠음. 이미 지나간 지점을 제외하는 코드를 안 넣어서ㅋㅋㅋ 안 넣어도 될 거라고 생각했는데 다시 생각해보니까 결국 그러면 겹쳐서 같은 계산을 여러 번 하게 되더라... 그래서 넣음

근데도 계속 메모리 초과가 나는 거임... 그래서 다른 사람들 풀이도 보고 했는데 나랑 푼 방식이 같아서 도저히 도움이 안 됐음!! 그래서 결국은 챗지피티한테 물어보았고... 그가 내린 결론은

다음 노드를 저장하는 배열을 지우세요!

였다.

이게 뭐가 큰 차이가 있지...? 하는 마음으로 진짜 지워봤는데, 정말 놀랍게도 됐다!
생각보다 매번 배열에 저장하는 게 메모리를 많이 먹나봄...?
그래서 앞으로는 꼭 필요한 경우 아니면 배열을 쓰지 말아야겠다... 라는 결론을 내렸다.

---

답을 얻은 코드는 여기

#include <iostream>
#include <queue>

using namespace std;

const int MAX_N = 1e5;

int bfs (int n, int k) {
    queue<int> q;
    bool is_used[MAX_N+1] = {false};
    int cnt = 0;

    if (n == k) return 0;

    q.push(n);
    is_used[n] = true;

    while (!q.empty()) {
        int len = q.size();
        cnt++;
        for (int i = 0; i < len; i++) {
            int node = q.front();
            q.pop();
            if (node == k) {
                return cnt - 1;
            }
            
            if (node - 1 >= 0 && node - 1 <= MAX_N && !is_used[node-1]) {
                q.push(node - 1);
                is_used[node-1] = true;
            } 
            if (node +1 >= 0 && node +1 <= MAX_N && !is_used[node+1]) {
                q.push(node+1);
                is_used[node+1] = true;
            }
            if (node *2 >= 0 && node *2 <= MAX_N && !is_used[node*2]) {
                q.push(node*2);
                is_used[node*2] = true;
            }
           
        }
    }
    return -1;
}

int main() {
    int n, k;
    cin >> n >> k;

    cout << bfs(n, k);
}