경로 구하기 문제 질문드립니다.!!

앞으로 이런 질문 가져오실 때는 문제 링크까지 같이 가져오셔야 답변 드리기가 편합니다.

https://115.20.177.81/problem.php?id=1963

이미 탐색한 경로를 중복해서 탐색해 시간초과가 납니다. v의 사용을 좀만 고쳐보세요.

그리고, 앞으로의 실수를 줄이기 위해서라도 C++ 연습 많이 하셔야 할것 같습니다.


추가적인 코드 리뷰 필요하시면 낮에 해드리겠습니다.

중ㅋ벅ㅋ제거

#include <iostream>
#include <vector>

int N, M, S, E;
int data[ 16 ][ 16 ] = { 0 };
int ch  [ 16 ] = { 0 };
std::vector< int > v;

auto dfs(int k) -> void {
    ch[ k ] = 1;
    v.push_back(k);

    if(k == E) {
        for(auto i: v)
            printf("%d ", i);

        std::exit(0);
    }

    for(int i = 1; i <= N; ++i)
        if(data[ k ][ i ] && !ch[ i ])
            dfs(i);

    v.pop_back();
}

auto main() -> int {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < M; ++i) {
        int t1, t2;

        scanf("%d %d", &t1, &t2);
        data[ t1 ][ t2 ] = 1;
        data[ t2 ][ t1 ] = 1;
    }

    scanf("%d %d", &S, &E);
    dfs(S);

    return 0;
}

처음에 올려주신대로 dfs 함수를 사용하는 버전입니다.

#include <iostream>
#include <vector>

#define NYA(lable, cond) lable: while(cond)

using Pii = std::pair< int, int >;

auto main() -> int {
    int N, M, S, E;
    int data[ 16 ][ 16 ] = { 0 };
    int ch  [ 16 ] = { 0 };
    std::vector< Pii > v;

    scanf("%d %d", &N, &M);

    for(int i = 0; i < M; ++i) {
        int t1, t2;

        scanf("%d %d", &t1, &t2);
        data[ t1 ][ t2 ] = 1;
        data[ t2 ][ t1 ] = 1;
    }

    scanf("%d %d", &S, &E);
    ch[ S ] = 1;
    v.emplace_back(S, 1);

    NYA(loop1, v.back().first != E) {
        for(int& i = v.back().second; i <= N; ++i)
            if(data[ v.back().first ][ i ] && !ch[ i ]) {
                ch[ i ] = 1;
                v.emplace_back(i++, 1);
                goto loop1;
            }

        v.pop_back();
    }

    for(auto i: v)
        printf("%d ", i.first);

    return 0;
}

이건 재귀를 사용하지 않는 버전입니다. vsecondfor문을 어디까지 돌았는지에 대한 정보를 저장합니다. NYA 매크로는 다소 테크닉적인 부분이므로, 유의해서 사용하시기 바랍니다.