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

문제: 사이클이 없는 그래프 G의 한 정점에서 다른 정점까지 이동할 수 있는 경로는 1가지만 존재한다.
그래프 G와 시작정점 s, 도착정점 e를 입력받아 s로부터 e까지의 경로에 포함되는 정점들을 순서대로 출력하는 프로그램을 작성하시오.

입력: 첫 줄에 정점의 개수 n(2<n<=10)과 간선의 개수 m(=n-1)이 입력된다.
둘째줄부터 인접한 2개의 정점이 m+1째 줄까지 입력된다.
마지막 줄에 시작정점 s와 도착정점 e가 입력된다.
단 정점은 1 이상의 정수로 표현되며, 비어있는 수는 없다고 가정한다.

출력: 시작정점 s로부터 도착정점 e까지의 경로에 포함되는 정점들을 방문 순서대로 출력한다.

#include<stdio.h>
#include<stack>
using namespace std;
stack<int>st;
int n,m,s,e,p,q;
int a[11][11],v[11],ans[11];
void visit(int k){
    st.push(k);
    v[k]++;
    return;
}
void dfs(int k){
    int i;
    while(st.top()!=e){
        for(i=1;i<=n;i++){
            if(a[st.top()][i]&&!v[i]){
                visit(i);
                dfs(i);
            }
        }
        if(i==n) st.pop();
    }
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int v=1;v<=m;v++){
        scanf("%d%d",&p,&q);
        a[p][q]=a[q][p]=1;
    }
    scanf("%d%d",&s,&e);
    v[s]++;
    st.push(s);
    dfs(s);
    int z=0;
    while(!st.empty()){
        z++;
        ans[z]=st.top();
        st.pop();
    }
    for(int j=z;ans[j];j--)
        printf("%d ",ans[j]);
    return 0;
}

testcase는 맞게 나오는데 시간 초과가 뜨네요ㅠㅠㅠ
뭐가 문제일까요…고수님들 알려주세요~!!!

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

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

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

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


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

중ㅋ벅ㅋ제거

넵 초보라서 잘 몰랐습니다ㅜㅜㅜ 앞으로는 명심하겠습니다.!!

v사용을 어떻게 고쳐야 할지 모르겠어요ㅠㅠ

#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 매크로는 다소 테크닉적인 부분이므로, 유의해서 사용하시기 바랍니다.