AvoidYourProfessor 관련 질문 드립니다.

  • chochogogo
    chochogogo

    안녕하세요?
    바쁘신 중에 또 질문드려 죄송합니다...

    해당 문제 풀이 관련하여 하기와 같이 동작하는 알고리즘을 설계, 구현해 보았는데요..

    1. 다익스트라 이용하여 모든 노드에 이르는 최단 거리 구함.
    2. start 정점을 1로 하고 완전 탐색 실시 하는데, 방문 하려는 노드까지 오는 cost가 다익스트라를 이용해 구한 결과와 동일한 경우에만 계속 탐색 실시.
    3. 최종 목적지에 도달하면, 해당 목적지에 오는데 거쳐간 cnt++ (예를 들어 1에서 출발하여 최종 목적지 8이라 할때, 경로가 1 3 4 8이라 하면 cnt[1]++, cnt[3]++, cnt[4]++, cnt[8]++
    4. 주인공이 방문 하려는 곳이 2일 경우 cnt[2] 나누기 GDC(cnt[2], cnt[8]) / cnt[8] 나누기 GDC(cnt[2], cnt[8]) 출력

    이렇게 알고리즘을 구현했는데....
    TC 20개도 못돌리더라구요...(타임아웃)

    혹시 알고리즘 설계가 완전 잘못 된 것일까요....

    조언 부탁드립니다.
    수고하십시오~!


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

    네, 완전 탐색으로는 시간 안에 찾을 수가 없습니다. 최단 경로가 엄청나게 많은 그래프들을 만들 수 있거든요.


    8년 전 link
  • chochogogo
    chochogogo

    네.. ㅎㅎ
    그 case를 생각 몬했내요..
    감사합니다~!


    8년 전 link

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