BRAVEDUCK - 오류

  • skylife927
    skylife927

    https://algospot.com/judge/problem/read/BRAVEDUCK
    1. 처음노드 + 중간노드 + 도착노드 (arr배열에 만들어주기)
    2. 각 노드사이의 거리를 이차원 배열로 만들어(dNode)
    (점프할 수 있는) 그래프를 만들수 있는 밑거름 만들기
    3. 그래프 노드(gNode)를 가지고 DFS탐색을 통해
    마지막 노드까지 갈 수 있는지 파악하여 bool값 을 통해 출력하기

    예제는 잘나오지만, 돌려보면 오류가 나옵니다..

    #include <iostream>
    #include <math.h>
    #include <stdlib.h>
    #define MAX_N 120
    
    using namespace std;
    
    int arr[MAX_N][2];
    int visit[MAX_N];
    int dNode[MAX_N][MAX_N];
    int gNode[MAX_N][MAX_N];
    int J = 0;
    int N = 0;
    bool isVisit = false;
    void DFS(int startNode){
        visit[startNode] = 1;
        int i=0;
        while(gNode[startNode][i] != 0){
            if(!visit[gNode[startNode][i]]){
                DFS(gNode[startNode][i]);
            }
            i++;
        }
        if(visit[N+2]) isVisit = true;
    }
    
    
    void push(int iNode, int jNode){
        int i=0;
        while(gNode[iNode][i] != 0){
            i++;
        }
        gNode[iNode][i] = jNode;
    }
    
    void makeGraph(){
        //gNode에다가 연결된 점을 다 넣어보자.
        for(int i=1; i<=N+2; i++){
            for(int j=1; j<=N+2; j++){
                if(dNode[i][j] > 0){
                    //i에 해당하는 노드에 연결고리노드 j를 달자
                    //하지만 이때 주의할 점은 값이 이미 있다면 그 다음 노드에 넣자.
                    push(i,j);
                }
            }
        }
    }
    
    
    void calculate(){
        //dNode의 이차원 배열에 노드와 노드 사이의 거리를 나타내보자
        //자기자신은 모두다 0으로 셋업시키기
        for(int i=1; i<=N+2; i++) dNode[i][i] = 0;
    
        //노드와 노드 사이의 거리를 측정하기
        for(int i=1; i<=N+2; i++){
            for(int j=1; j<=N+2; j++){
                // i노드에서 j노드까지 가는 거리를 저장한다.
                // dNode[i][j], arr[i]의 [0][1] x,y   arr[j]의 [0][1] x,y
                // 만약 거리가 J를 넘어서게 된다면 0으로 바꾸기
                //그리고 i>j 인경우에만 계산하면 됩니다. (어차피 중복계산이니까)
                if(j>i){
                    int sX,sY,tX,tY;
                    sX = arr[i][0];
                    sY = arr[i][1];
                    tX = arr[j][0];
                    tY = arr[j][1];
                    int x = abs(sX-tX);
                    int y = abs(sY-tY);
                    int distance = x*x + y*y;
                    if(J>=sqrt((double)distance))
                        dNode[i][j] = distance;
                }
            }
        }
    
    }
    
    void init(){
        for(int i=0; i<MAX_N; i++){
            arr[i][0] = 0;
            arr[i][1] = 0;
            visit[i] = 0;
        }
        for(int i=0; i<MAX_N; i++){
            for(int j=0; j<MAX_N; j++){
                dNode[i][j] = 0;
                gNode[i][j] = 0;
            }
        }
        N=0;
        J=0;
        isVisit = false;
    }
    
    int main(int argc, char** argv)
    {
        int test_case;
        int T;
    
        cin >> T;
        for(test_case = 0; test_case < T; test_case++)
        {
            //J 1000, N 100
    
            int x1, x2, y1, y2;
    
    
            init();
    
            cin>>J>>x1>>y1>>x2>>y2>>N;
            //처음과 끝 노드 설정
            arr[1][0] = x1;
            arr[1][1] = y1;
            arr[N+2][0] = x2;
            arr[N+2][1] = y2;
            //중간에 위치한 노드의 설정
            for(int i=2; i<=N+1; i++){
                int tX, tY;
                cin>>tX>>tY;
                arr[i][0] = tX, arr[i][1] = tY;
            }
    
            //각 노드사이의 거리를 이차원 배열로 나타내기
            calculate();
    
            //노드에 대한 그래프를 만들기
            makeGraph();
    
            //그래프를 DFS로 탐색, 단 방문한 노드에 대해서는 방문하지 않기.
            //탐색 중 마지막 노드 N+2 노드를 방문하면 가능함, DFS로 다 찾아봤는데 
            //못찾았따면 NO
            DFS(1);
            if(isVisit) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    
        return 0;
    }
    

    8년 전
2개의 댓글이 있습니다.
  • skylife927
    skylife927

    push(i, j)
    push(j, i)
    역으로 연결 안해줘서 오답이였네요.
    정답나왔습니당~~


    8년 전 link
  • Pekaz
    Pekaz

    짝짝짝~


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