AVOID 문제 질문드립니다.

  • juhosung
    juhosung

    AVOID 문제를 풀다가 헷갈리는 부분이 있어서 질문드립니다.

    문제에서 답의 출력을 기약분수로 나타내야 된다고 적혀있습니다.

    그렇다면 입력으로 들어온 간선(E)의 갯수가 0개이거나, 출발점에서 도달점까지 가는 경로의 수가 0개일 경우
    어떤식으로 나와야 할지 궁금합니다.

    혹시 문제에 대한 이해가 부족해서 잘못된 방향(0에 대한 예외처리)으로 생각하는가 싶어, 제가 생각한 확률을 구하는 방법을 적어보겠습니다.
    **확률 : N을 도중에 거치면서 1 ~ V로 가는 모든 최단 경로의 수 / 1 ~ V로 가는 모든 최단 경로의 수 입니다.

    여기서 입력으로 들어온 간선의 갯수가 아예 없거나, 1 ~ V까지 갈 수 있는 경로가 존재하지 않을 경우

    이럴 경우 분모와 분자간에 최대공약수가 0이됩니다.

    그래서 분모와 분자를 0으로 나누면 RTE가 발생(해당 문제를 제출하고 RTE 발생을 확인.) 하기 때문에, 0/0으로 출력하게 예외처리를 했습니다.

    0/0으로 출력하도록 하는게 맞는건가요??.

    아니면 제가 문제에 대한 이해를 확실하게 하지 못해서, 이런 경우를 생각하는 걸 까요?

    답변 부탁드립니다.

    요약 : 분모가 0인 경우가 있나요? 만약에 있다면 어떤 식으로 출력해야 되나요?


    5년 전
12개의 댓글이 있습니다.
  • Being
    Being

    예제에서 마지막 출력의 경우를 0/1로 간주하고 있으니, 0/1을 출력하시면 되는 게 아닐까 싶습니다.


    5년 전 link
  • juhosung
    juhosung

    아 마지막 출력에서는 분모(1~V까지이어지는 경로의 수)는 0이 아니고, 분자만 0이기 때문에 제가 질문한 문제형태랑은 좀 다른 것 같아요.


    5년 전 link
  • juhosung
    juhosung

    1
    3 0 2
    1 2
    문제해결 하신분들 입력이 이렇게 들어올 경우 어떻게 출력되나요..?


    5년 전 link
  • Being
    Being

    음, 1번에서 8번 노드까지 가는 최단 경로 중 7번 노드를 거치는 경우가 가능한가요?


    5년 전 link
  • juhosung
    juhosung

    7번 노드를 거치는 경우의 수는 없습니다.
    음 제가 궁금한거는, '출발지에서 도착지까지 가는 경로가 아예 없을 경우 어떻게 출력될까' 입니다.
    문제예시에서는 1번에서 8번까지 가는 최단경로는 있기 때문에, 질문한 형태랑은 다르네요.
    1번에서 8번 노드까지 가는 경로가 아예 없을 경우, 어떻게 출력되는지 궁금하네요


    5년 전 link
  • Being
    Being

    그렇군요. 그런 경우는 없다고 가정하셔도 될 것 같습니다.


    5년 전 link
  • juhosung
    juhosung

    음.. 그런데 문제 조건에서 '도로의 수 E (0 <= E <= V(V-1)/2)' 라는 조건이 있는데.. 조건대로라면 E가 0일 경우에는 출발지에서 도착지 가는 경로가 없는 케이스가 들어올수있지 않나요??


    5년 전 link
  • Being
    Being

    데이터를 한번 살펴봐야겠지만, 아마 타이트하게 잡은 바운드는 아닐 것 같네요.


    5년 전 link
  • Being
    Being

    일단 데이터에는 경로가 없는 경우는 없습니다. 경로가 없는 경우 확률 자체가 성립하지 않으니 그냥 없다고 생각하셔도 될 것 같습니다. 문제 설명의 경우 원 출제자분과 논의 후 갱신하겠습니다.


    5년 전 link
  • juhosung
    juhosung

    넵 감사합니다


    5년 전 link
  • juhosung
    juhosung

    음 제가 일종의 트릭으로 간선을 입력받는 부분에서, 입력 정보에서 도착노드가 V가 있을 경우에 플래그 변수를 TRUE(플래그 변수 초기값 : FALSE)로 바꾸도록 했습니다. 그리고 간선 입력 이후에 플래그 변수가 FALSE일 경우에 무한루프를 돌도록 코드를 변경했습니다. 그리고 다시 제출했는데 시간초과가 뜨네요.


    5년 전 link
  • Being
    Being

    데이터엔 문제가 없어 보입니다. 제출하신 코드를 보니 도로를 일방통행이라고 가정하신 것 같네요.


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