BRAVEDUCK C++ 어떤 케이스가 오답이 나오는지 모르겠습니다.

  • naka15
    naka15

    현재 위치에서 갈 수 있는 돌을 canGo vector에 넣고
    방문한 돌들은 remainList에서 제거하는 방식으로
    길을 찾아가는 알고리즘인데 java에서는 같은 알고리즘으로
    정답이 나오는데 C++에선 오답이 나옵니다.
    어떤 케이스가 오답이 나오는지 알수 있으면
    해결할 수 있을것 같은데 도움 부탁드립니다.
    질문 처음 올리는데 지적할 부분있으면 말씀해 주세요.
    BRAVEDUCK

    #include<iostream>
    #include<list>
    #include<string>
    #include<vector>
    #include<math.h>
    
    using namespace std;
    
    int jump;
    int endx;
    int endy;
    struct vertex{
        int x;
        int y;
    }end;
    list<vertex> remainList;
    bool haspath;
    
    void findPath(vertex nowLoc){
        vector<vertex> canGo;
    
        list<vertex>::iterator pos = remainList.begin();
    
        double x=0;
        double y=0;
        for(pos; pos!=remainList.end();){
            x=pos->x;
            y=pos->y;
            //temp는 현재위치에서 대상 돌과의 거리
            double temp = sqrt(pow((double)nowLoc.x-x,2)+pow((double)nowLoc.y-y,2));
    
    
            //점프 가능한 거리면 현재위치에서 방문할 수 있는 돌, canGo리스트에 삽입
            if(temp<=jump){         
            //갈수 있는 돌이 목표지점이면 true
                if(x==endx&&y==endy){   
                 haspath=true;
                 return;
                }
                //현재 위치에서 방문할수 있는 돌입력 후
                //두 번 방문 하지 않기 위해 리스트에서 제거
                canGo.push_back(*pos);
                pos=remainList.erase(pos);
            }else{
                pos++;
            }
        }
    
        if(canGo.size()==0){
            return;
        }
        //갈 수 잇는 돌들을 모두 방문해 본다
        for(int i=0; i<canGo.size(); i++){
            if(haspath==true)
                return;
            nowLoc = canGo[i];
            findPath(nowLoc);
        }
    
    }
    
    
    int main(){
    
        int cases;
        cin>>cases;
        string *result = new string[cases];
    
        for(int i=0; i<cases; i++){
            haspath=false;
            //점프 거리 입력
            cin>>jump;
    
            //시작점 입력
            vertex start;
            cin>>start.x;
            cin>>start.y;
            //끝점 입력
            vertex end;
            cin>>end.x;
            cin>>end.y;
            endx=end.x;
            endy=end.y;
            //돌 개수
            int vertexnum;
            cin>>vertexnum;
            //돌 좌표 입력
    
            for(int j=0; j<vertexnum; j++){
                vertex t;
                cin>>t.x;
                cin>>t.y;
                remainList.push_back(t);
            }
            remainList.push_back(end);
            findPath(start);
            if(haspath==true){
                result[i]="YES";
            }else{
                result[i]="NO";
            }
    
        }//for cases 끝
        //결과 출력
        for(int i=0; i<cases; i++){
            cout<<result[i]<<endl;
        }
    
    }//main 끝
    

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

    간단히 살펴봤는데, remainList가 초기화되지 않고 있습니다.


    8년 전 link
  • naka15
    naka15

    아, 그렇네요.
    좀더 꼼꼼히 봐야겠네요
    Toivoa님 덕분에 해결됬습니다. 정말 감사합니다!


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