Avoid 또 질문드립니다...ㅠㅠㅠㅠ

  • chochogogo
    chochogogo

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

    다름이 아니오라 기본 알고리즘이 잘못 됬다는 것을 느끼고 변형 시켜 보았는데요...

    1. 기존 1)다익스트라 이용하여 모든 노드에 이르는 최단 거리 구함.

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

    3)주인공이 방문 하려는 곳이 2일 경우 cnt[2] 나누기 GDC(cnt[2], cnt[8]) / cnt[8] 나누기 GDC(cnt[2], cnt[8]) 출력
    이렇게 알고리즘을 구현했는데....

    1. 변경 1)다익스트라를 각 노드를 시작정점으로 하여 각 노드로부터 다른 모든 노드에 이르는 최단 거리 구함.(플로이드 구현)

    2)start 정점을 1로 하고 완전 탐색 실시 하는데, 함수 선언은
    func(시작 정점, end 정점)로함.

    방문 하려는 노드까지 오는 cost가 다익스트라를 이용해 구한 결과와 동일한 경우에만 계속 탐색 실시.
    && 다익스트라(플로이드 버전)의 결과가 distance[start][end]에 저장되어 있다면
    distance[1][최종 목적지] == distance[1][임의의 노드] + distance[임의의 노드][최종목적지] 인 경우만 탐색 실시

    3)
    주인공이 방문 하려는 곳이 2일 경우
    result1 = func(1, end 정점)
    result2 = func(1, 2) * func(2, end정점)

    result2 나누기 GDC(result2, result1) / result1 나누기 GDC(result2, result1) 출력
    이렇게 알고리즘을 구현했는데....

    여전히...TC 20개도 못돌리더라구요...(타임아웃)

    혹시 알고리즘 팁 있으면 조언 부탁드립니다...ㅠㅠ
    인터넷에서 해당 문제 관련 정보를 찾으려는데 도저히 못찾겠어서요...ㅠㅠ


    9년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    어떻게 하셔도 완전 탐색은 안될겁니다. 동적 계획법을 쓰셔야 합니다.


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