World Wide Web - 구름LEVEL
World Wide Web
Quiz Info
Quiz Info
World Wide Web
100points
Participant
1
Solved Rate
100%
0
0

WWW, 즉 World Wide Web이라고 하는 인터넷 세계에서는 어떤 페이지에서 원하는 페이지로 이동하는데에 평균적으로 19회의 마우스 클릭이 필요하다고 합니다.

우리는 이 페이지 이동을 컴퓨터 자료구조인 그래프로 바꾸어 각 페이지를 노드라고 생각하고 페이지 간에 연결된 선을 간선으로 생각하도록 하겠습니다.

                            

그림을 통해 문제를 설명하도록 하겠습니다.

1번 페이지에서 2번으로 가기 위한 최소 클릭 수로 2회의 클릭이 필요하고, 3번으로 가기 위해서는 1회, 4번은 3회 그리고 5번은 4회 입니다.

2번 페이지에서는 1, 3, 4, 5번 페이지로 가기위해서 각각 순서대로 3, 1, 1, 2회의 클릭,

3번 페이지에서는 1, 2, 4, 5에 각각 4, 1, 2, 3회,

4번 페이지에서는 1, 2, 3, 5에 각각 2, 4, 3, 1회,

5번 페이지에서는 1, 2, 3, 4에 각각 1, 3, 2, 4회의 클릭이 필요합니다.

이는 20개의 비교 대상 노드쌍에 총 37회의 클릭이 필요한 꼴이므로 37/20, 평균 1.85회의 클릭이 필요하다고 할 수 있습니다.

이렇게 페이지 간의 연결관계가 주어질 때, 페이지 이동에 필요한 평균 클릭 수를 출력하는 프로그램을 작성하십시오.

 

입력

한 줄에 한 쌍( x, y )씩 페이지 사이의 연결관계를 표현한다.

*x에서 y 방향( Directed Graph )으로의 간선이라고 생각할 것

출력

페이지 사이의 평균 클릭 수( 소수점 2번째 자리까지 )



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
12
24
13
31
43
00
Output
1.83
Example 2
Input
12
14
42
27
71
00
Output
1.75
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)