인프런 커뮤니티 질문&답변

안녕하세요 명운님

강의속 코드에서 turn = 1로 초기화 하고 b 에다가 turn을 더하는 방식으로 코드를 작성하셨는데 turn = 0 으로 초기화 하고, 이에 맞게 코드를 재작성하니 원하는 답이 나오지 않아서 질문 드립니다.

>> 이게 1이 아니라 0으로 초기화를 했다고 하시는거죠?

음.. 근데

int bfs(int N, int K) {
    int turn = 1;

turn이 1로 초기화가 되어있어서요.

그래서 코드를 전체적으로봤는데요.

이게 좀 꼬여있는게 있는 거 같습니다.

#include <bits/stdc++.h>
using namespace std;

int N, K, visited[2][500005];
bool flag;

int bfs(int N, int K) {
    int turn = 1;
    queue<int> q;
    q.push(N);
    visited[0][N] = 1;
    while (q.size()) {
        K += turn;
        if (K >= 500001) return -1;
        if (visited[turn % 2][K]) {
            flag = 1;
            return turn;
        }
        int qsize = q.size();
        for (int i = 0; i < qsize; i++) {
            int here = q.front(); q.pop();  
            cout << "HERE : " << here << " " << turn << " : " << K << "\n";
            if (here == K) {
                flag = 1;
                return turn;
            }
            for (int there : {here + 1, here - 1, here * 2}) {
                if (there < 0 || there >= 500001) continue;
                if (visited[turn % 2][there]) continue;                 
                visited[turn % 2][there] = visited[(turn + 1) % 2][here] + 1;
                q.push(there);
            } 
        }
        turn++;
    }
    return -1;
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> K;
    int res = bfs(N, K);
    if (flag) cout << res << '\n';
    else cout << - 1 << '\n';
    return 0;
}

이렇게 해보시면 5 17을 넣었을 때

5 17

HERE : 5 1 : 18

HERE : 6 2 : 20

HERE : 4 2 : 20

HERE : 10 2 : 20

HERE : 7 3 : 23

HERE : 12 3 : 23

HERE : 3 3 : 23

HERE : 8 3 : 23

HERE : 11 3 : 23

HERE : 9 3 : 23

HERE : 20 3 : 23

이런식으로 나옵니다. 즉, 동생이 한번 더 움직이고 있습니다.

이부분에 대한 로직을 수정해보시겠어요?

또 질문 있으시면 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다.

감사합니다.