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

안녕하세요 현우님 ㅎㅎ

visited 참조가 가장 끝까지 발생할 수 있으므로 이렇게 해주어야 합니다.

int visited[2][MAX + 1];

그리고 while문을 빠져나왔을 때의 예외처리, N == K가 같을 때의 처리를 해주어야 합니다.

나머지 코드부분은 잘 짜셨습니다. ㅎㅎ

제가 다듬은 코드는 다음과 같습니다.

#include <bits/stdc++.h>
#define MAX 500000

using namespace std;

int N, K, turn = 1;
int visited[2][MAX + 1];

void print() {
    for (int i = N; i <= 2 * K; i++) {
        cout << visited[0][i] << " ";
    }

    cout << "\n";
    for (int i = N; i <= 2 * K; i++) {
        cout << visited[1][i] << " ";
    }

    cout << "\n";
}

int main() {
    cin >> N >> K;
    if (N == K) {  // 시작 위치와 목표 위치가 같다면
        cout << 0;
        return 0;
    }

    visited[0][N] = 1;

    queue<int> q;
    q.push({N});

    while (!q.empty()) {
        int qsize = q.size();

        K += turn;

        if (K > 500000) {
            cout << -1;
            return 0;
        }

        if (visited[turn % 2][K]) {
            cout << turn;
            return 0;
        }

        for (int i = 0; i < qsize; i++) {
            int now = q.front(); q.pop();

            for (int next : {now + 1, now - 1, now * 2}) {
                if (next < 0 || next > MAX || visited[turn % 2][next]) continue;
                visited[turn % 2][next] = visited[(turn + 1) % 2][now] + 1;
                if (next == K) {
                    cout << turn;
                    return 0;
                }
                q.push(next);
            }
        }

        turn++;
    }

    cout << -1;

    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

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

감사합니다.

강사 큰돌 올림.