작성한 질문수 79

1

안녕하세요 유태님 ㅎㅎ

17 16 15까지만 출력이 됩니다.

->

17의 경우 17 16 15가 출력이 되어야 합니다.

로직이 올바르게 짜여있는 것인지 궁금합니다.

->

prev 를 하신 것은 잘하셨지만 이렇게 하셔야 합니다.

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

const int max_n = 500000; 
int visited[2][max_n + 4], a, b, ok, turn = 1;
int prevPos[2][max_n + 4];  
vector<int> path;

void printPath(int turn, int b) {
    while (b != a) {  
        path.push_back(b);
        b = prevPos[turn % 2][b];
        turn--;
    }
    path.push_back(a);  
    reverse(path.begin(), path.end());  
    
    cout << "경로 : ";
    for (int pos : path) {
        cout << pos << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> a >> b;
    if(a == b) {
        cout << 0 << "\n";
        cout << "Path: " << a << "\n";
        return 0;
    }

    queue<int> q;
    visited[0][a] = 1;
    q.push(a);

    while(q.size()) {
        b += turn;
        if(b > max_n) break;  

        if(visited[turn % 2][b]) {
            ok = true;
            break;
        }

        int qSize = q.size();
        for(int i = 0; i < qSize; i++) {
            int x = q.front(); q.pop();
            for(int nx : {x + 1, x - 1, x * 2}) {
                if(nx < 0 || nx > max_n || visited[turn % 2][nx]) continue;
                visited[turn % 2][nx] = visited[(turn + 1) % 2][x] + 1;
                prevPos[turn % 2][nx] = x;  

                if(nx == b) {
                    ok = 1;
                    prevPos[turn % 2][b] = x;   
                    break;
                }
                q.push(nx);
            } 
            if(ok) break;
        }
        if(ok) break;
        turn++;
    }

    if(ok) {
        cout << turn << "\n";
        printPath(turn, b);  
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

감사합니다.

0

안녕하세요, 인프런 AI 인턴입니다. 한유태님.

동생을 찾는 최단 경로와 경로 출력 문제에 대한 질문을 주셨네요. 비슷한 개념을 활용한 문제들이 있었으니, 아래 답변에서 몇 가지 중요한 포인트와 함께 참고할 수 있는 기존 답변을 안내드리겠습니다.

우선, 가장 빠른 시간으로 동생을 찾는 방법의 수를 출력하는 방식이 알맞게 구현되었는지 고민해보면, BFS를 사용하여 탐색하면서 최단 경로 (즉, 최소 시간)를 찾아야 합니다. <보완점: 주어진 코드 예시>

1. 가장 빠른 시간으로 동생을 찾는 방법의 수 구현:

   • BFS의 큐를 사용해 각 정점에 도달하는 최단 시간을 기록하고, 최단 시간에 도달한 여러 경로를 카운팅해야 합니다.
     
   • BFS 탐색 중 방문한 모든 경로를 추적하며 prv 배열을 적절히 사용하여 동생 위치를 찾는 과정을 가시적으로 유지해야 합니다.
     

2. prv 배열 문제점:

   • prv 배열을 1차원에서 2차원으로 변경하는데 따른 문제는, 짝수 루프와 홀수 루프의 차이에 의해 발생할 수 있습니다. 주어진 문제의 특성상 어느 시간에 어느 위치에 도달했는지 구분이 필요합니다.
     
   • cnt--와 같은 변수 접근은 정확한 상태를 유지하기 어려워 질 수 있으니, 방문 배열이나 prv 배열을 적절히 활용하여 경로를 추적해야 합니다.
     

3. 경로 중복 문제:

   • BFS 탐색의 특성상 여러 경로가 만들어질 수 있으며, 17 16 15 후에 14가 출력되지 않는 경우는 경로 추적 알고리즘의 특성을 갈아보셔야 해요. 예를 들어 상태 업데이트 문제나 중간 상태가 없어지는 경우라면 14로 가는 경로가 사라질 수 있어요.
     

다음은 비슷한 주제를 다룬 이전 답변 링크입니다:

• 3-I 질문 있습니다 (여기서는 홀짝을 고려한 BFS 최적화가 핵심입니다)
  
• 3-I 17071 문제 질문있습니다 (실시간 이동 시나리오에서의 경로 검토)
  
• 13913_숨바꼭질4 (BFS를 활용한 숨바꼭질 최적 경로 및 시간 구현)
  

이러한 답변들을 살펴보시면 더 뚜렷한 그림이 그려지리라 생각됩니다. 위 답변들을 통해 구체적인 로직을 개선해 보시면 좋을 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.