3-I 응용 질문있습니다 :)

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-I

해결된 질문

작성

안녕하세요 선생님 🙂

이 문제에 숨바꼭질 2번의 가장 빠른 시간으로 동생을 찾는 방법의 수와 숨바꼭질 4번의 이동 경로를 출력하는 방법을 넣어보고 싶어서 응용을 해봤습니다.

http://boj.kr/140dd82426b947a59d51672a9bda4d0a

가장 빠른 시간으로 동생을 찾는 방법의 수를 출력하는 로직이 올바르게 짜여있는 것인지 궁금합니다.

int prv[2][500004];

for (int i = K; i != N; i = prv[cnt%2][i])
{
	vec.push_back(i);
        //cnt--;
}
vec.push_back(N);

reverse(vec.begin(), vec.end());

for (const auto& v : vec)
{
	cout << v << " ";
}

prv배열을 2차원으로 했을 때, 1, 10을 입력하면 올바른 값이 나오지만 5, 17과 17, 5는 출력 자체가 되지 않습니다. prv배열을 1차원으로 했을 때는 5, 17과 17, 5는 출력이 되지만(5, 17만 올바른 값 출력) 1, 10은 출력 자체가 되지 않습니다. 혹시나 해서 for문에 cnt--를 넣어봤지만, 제대로 출력되던 1, 10조차 출력 자체가 되지 않았습니다. 이유와 해결방법이 궁금합니다.

17 -> 16, 15, 14, 15
5  -> 6, 8, 11, 15

위의 경우처럼 중복되는 경로가 있는 경우는 17 16 15까지만 출력이 됩니다. 14가 출력되지 않는 이유는 16 뒤에 출력되는 15가 첫번째 방문하는 15가 아닌 마지막 15를 방문해서 그런걸로 이해했는데 제대로 이해한게 맞을까요?

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 유태님 ㅎㅎ

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;
}

감사합니다.

인프런 AI 인턴

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

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

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

가장 빠른 시간으로 동생을 찾는 방법의 수 구현:
- BFS의 큐를 사용해 각 정점에 도달하는 최단 시간을 기록하고, 최단 시간에 도달한 여러 경로를 카운팅해야 합니다.
- BFS 탐색 중 방문한 모든 경로를 추적하며 prv 배열을 적절히 사용하여 동생 위치를 찾는 과정을 가시적으로 유지해야 합니다.
prv 배열 문제점:
- prv 배열을 1차원에서 2차원으로 변경하는데 따른 문제는, 짝수 루프와 홀수 루프의 차이에 의해 발생할 수 있습니다. 주어진 문제의 특성상 어느 시간에 어느 위치에 도달했는지 구분이 필요합니다.
- cnt--와 같은 변수 접근은 정확한 상태를 유지하기 어려워 질 수 있으니, 방문 배열이나 prv 배열을 적절히 활용하여 경로를 추적해야 합니다.
경로 중복 문제:
- BFS 탐색의 특성상 여러 경로가 만들어질 수 있으며, 17 16 15 후에 14가 출력되지 않는 경우는 경로 추적 알고리즘의 특성을 갈아보셔야 해요. 예를 들어 상태 업데이트 문제나 중간 상태가 없어지는 경우라면 14로 가는 경로가 사라질 수 있어요.

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

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

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

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

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

3-I 응용 질문있습니다 :)