페이지 전환 > 문제은행

본문 바로가기


알고리즘 최단거리

1108 : 페이지 전환

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



인터넷이 발달하여 사람들이 웹서핑을 많이 하는데, 웹브라우져를 켜서 보통은 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 이다.
이 그래프에서 모든 쌍은 12쌍이 나오기 때문에 즉, 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보다 작은 수이다.



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


[Copy]
5
1 2
2 4
1 3
3 1
4 3
[Copy]
1.833




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