페이지 전환 > 문제은행



알고리즘 최단거리

1108 : 페이지 전환

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 733 회    시도횟수: 1662 회   



인터넷이 발달하여 사람들이 웹서핑을 많이 하는데, 웹브라우져를 켜서 보통은 19번의 클릭을 한다고한다.


페이지를 전환하는 상태가 아래 그래프와 같이 주어진다면,
 
7ce7f2eba5731c8babe39036322897a0_1449816

1번 페이지에서 2번, 3번, 4번 페이지로 갈 때의 가장 짧은 페이지 클릭 횟수는 1,1,2이고, 

2번 페이지에서 1번, 3번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 3,2,1이고,

3번 페이지에서 1번, 2번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 1,2,3이고, 

4번 페이지에서 1번, 2번, 3번 페이지로 가는 가장 짧은 페이지 클릭 횟수는 2,3,1이다.


이때, 가장 짧은 페이지 클릭 횟수의 합을 모두 구하면 1+1+2+3+2+1+1+2+3+2+3+1=22 이다.
이 그래프에서 모든 쌍은 1번에서 2번 페이지로 가기, 1번에서 3번 페이지로 가기, ..., 4번에서 3번 페이지로 가기, 
12쌍이 나오기 때문에 어떤 페이지에서 다른 페이지로 이동하는 평균 클릭 횟수는 22/12로 1.833이된다.




첫줄에 N(1≤N≤500)이 나온다. 다음줄부터 N개의 줄 각각에 i, j가 나오는데 이것은 i페이지에서 j페이지로 갈 수 있음을 의미한다. 또한 단 방향이므로, j에서 i로는 갈 수 없다. j에서 i로 갈 수 있으려면, 뒤의 줄에 j, i가 나와야 한다. 이때, 어떤 페이지에서 다른 페이지로 갈 수 없는 경우는 없도록 데이터가 입력된다. 또한 페이지의 번호는 1번 부터 i, j 값중 가장 큰 값이 페이지의 마지막 번호로 들어온다. 단, 페이지 번호는 500보다 작은 수이다.




출력은 어떤 페이지에서 다른 페이지로 이동하는 평균 클릭 횟수를 출력한다. 출력값으로는 소수 넷째자리에서 반올림하여 소수 셋째자리까지 출력한다.



5
1 2
2 4
1 3
3 1
4 3
1.833


최단거리

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.