GALLERY 감시카메라설치 질문입니다

  • 김창한
    김창한

    제가 사용한 알고리즘은 그리디 알고리즘입니다.

    1. 카메라가 닿는 노드를 포함하여 카메라가 설치되지 않은 노드들 중에서, 카메라가 닿지 않는 노드를 가장 많이 방문할 수 있는 노드를 선택 해 카메라를 설치합니다.

    2. 설치한 노드에서 방문 가능한 노드를 모두 카메라가 닿는 노드로 변경합니다.

      3.모든 노드에 카메라가 닿는지 검사 후, 모든 노드에 카메라가 닿으면 답을 출력하고, 아니면 위 과정을 다시 반복합니다.

    예시 입력은 다 맞게 나오고 나름대로 입력을 만들어서 풀어도 맞는데 왜 자꾸 오답이 뜨는지 모르겠습니다. 혹시 제가 틀린 알고리즘을 쓰고 있어서 그런지 궁금합니다.


    8년 전
1개의 댓글이 있습니다.
  • Signin
    Signin

    ㅇ
    ㅣ
    ㅇ
    ㅣ
    ㅇ-ㅇ-ㅇ
    ㅣ
    ㅇ
    ㅣ
    ㅇ

    와 같은 입력을 테스트해보기시길 권해드립니다.


    8년 전 link

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