신호 ROUTING 문제 오답질문입니다 !

  • sujae03
    sujae03

    ROUTING
    연습 문제
    라우팅 문제를 푸는데, 오답으로 처리가 됩니다.
    혹시 어떤부분에서 오답처리가 되는지 도움을 주실 수 있으신가요 ?

    자료구조 : vector를 이용하여 인접리스트를 만들었습니다.

    알고리즘 : vector로 만든 인접리스트를 기반으로
    DFS를 수행합니다.
    A노드에서 B노드로 갈 때, 가중치만큼 값이 곱해집니다.
    그리고 해당 값은 stack에 저장합니다.
    B가 더이상 유망하지 않다면 해당 값은 pop해줍니다.
    최초로 목적지까지 도착했을 때 값을 MIN으로 놔두고
    길목을 탐색할때마다 MIN보다 커질거 같으면 유망하지
    않다고 판단하고 탐색하지 않습니다. 이렇게 최종적으로
    가장 작은 값만 갖고있게되고, 해당 값을 출력해줍니다.

    무엇이 문제인지 도와주시면 감사하겠습니다 !

    #include <stdio.h>
    #include <iostream>
    #include <stack>
    #include <vector>
    #include <stdlib.h>
    
    using namespace std;
    
    int N; // 노드 수
    int vertex; //간선의 수
    
    int visit[10001] = { 0, };
    long double res = 1; // 결과값
    long double MIN_res = 1.7976931348623158e+308;
    vector<long double> arr[10001];
    stack<long double> s;
    stack<long double> s_val;  //값 비교용 stack
    
    
    /// 인접리스트 생성
    
    /// 추가사항: 양방향 그래프 될 수 있도록 해주고, (  O ) 
    ///           자료형 double로 바꿔준다. ( O )
    
    void input() {
        int node_a;
        int node_b;
        long double val;
        for (int i = 0; i < vertex; i++) {
            cin >> node_a >> node_b >> val;
            arr[node_a].push_back(node_b);
            arr[node_b].push_back(node_a);
            arr[node_a].push_back(val);
            arr[node_b].push_back(val);
        }
    
    }
    
    void DFS(int start) {
    
        if (start == N - 1) {  // 마지막노드에 도착하였다면.
            MIN_res = s_val.top();  //마지막노드까지 왔다는 것은, 최소의 값이라는 것을 의미하므로. 
            s_val.pop();
            return;
        }
    
        //들어오는 값 스택에 넣어주고
        s.push(start);
    
        // visit 해준다.
        visit[start] = 1;
    
        int temp_node = 0;
    
        for (int i = 0; i < arr[start].size(); i += 2) {
    
            temp_node = arr[start][i];  // 다음으로 갈 노드 
    
            if (!visit[temp_node] && (s_val.top()*arr[start][i+1])<MIN_res ) {  // 방문하지 않았고, 방문하지 않았다 하더라도 곱했을 경우 최소증폭보다 값이 크다면 X
                res = s_val.top()*arr[start][i + 1];
                s_val.push(res);
                DFS(temp_node);
            }
        }
    
    
        // 더이상 갈 곳이 없을때에는 pop해주려는 부분에 대해 visit 초기화 시켜주고, pop해준다.
        int temp = 0;
        temp = s.top();
        visit[temp] = 0;  
        s.pop();
        s_val.pop();
    
    
    
    }
    
    
    /// 초기화 함수
    void init() {
    
        MIN_res = 1000000;
        for (int i = 0; i < N; i++) {
            visit[i] = 0;
        }
    
        // vector에서 사용한 동적메모리 해제
        for (int i = 0; i < N; i++) {
            arr[i].clear();
        }
    }
    
    void Test();
    int main() {
    
    
        /// TestCase 입력
        int TestCase = 0;
        //freopen("in.txt", "r", stdin);
        cin >> TestCase;
        for (int i = 0; i < TestCase; i++) {
    
            /// 노드 수 입력
            cin >> N;
    
            /// 간선의 수 입력
            cin >> vertex;
    
    
            /// 간선정보 입력
            input();
    
            // Start : 0  , End : N-1 번
            /// DFS 
            s_val.push(1);  // 처음에 value 1 넣어주고 시작.
            DFS(0);
    
            cout.setf(ios::fixed);
            cout.precision(10);
            cout << MIN_res<<endl;
            init();
        }
        return 0;
    }
    
    /// Just Test
    void Test() {
    
    
        // 인접리스트 출력
        for (int i = 0; i < vertex; i++) {
            cout << "시작:" << i << " ";
            for (int j = 0; j < arr[i].size(); j += 2) {
                cout << " 정점:" << arr[i][j] << " " << " 값:" << arr[i][j + 1] <<"/";
            }
            cout << endl;
        }
    }
    
    {{i0bRJBvdDTZtAIOX}}
    

    8년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.