알고리즘 1108 페이지전환

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

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

 

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

Floyd 알고리즘을 사용하면 매우매우매우 쉽게 끝나는 문제. 한번 이동하면 클릭이 1씩 증가하므로 연결된 노드가 가중치가 1인 그래프와 같은 원리가 된다.

입력 받는 노드를 1, 나머지를 가중치 높게 잡은 뒤 Floyd 알고리즘으로 각 점에서 점으로 이동하는 최단거리를 구해주고, 배열의 행, 열 값이 같은 경우를 제외한 나머지를 더해주면 된다. (각 행에서 행, 열이 같은 경우를 제외하면 행 번호에서 다른 페이지로 이동하는 최소 클릭합이 된다.)

#include 

#define SIZE 500
#define INF 1000;

int dist[SIZE][SIZE] = { 0 };



int main() {
	int N;
	int i, j, k;
	double result = 0;
	int n=0;
	int x, y;
	int temp;
	scanf("%d", &N);

	for (i = 0; i < N; i++) {    //값을 입력받아 배열에 저장하고, 이들 중 가장 큰 값을 구한다.
		scanf("%d %d", &x, &y);
		dist[x - 1][y - 1] = 1;
		temp = (x > y ? x : y);
		n = (temp > n ? temp : n);
	}

	for (i = 0; i < n; i++) {    //연결되어 있지 않은 두 점의 가중치를 INF로 설정
		for (j = 0; j < n; j++) {
			if (!dist[i][j]) {
				dist[i][j] = INF;
			}
		}
		
	}



	for (i = 0; i < n; i++) {    //Floyd알고리즘 적용
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				if (dist[j][k] > dist[j][i] + dist[i][k])
					dist[j][k] = dist[j][i] + dist[i][k];
			}
		}
	}


	for (i = 0; i < n; i++) {    // 자기 자신으로 이동하는 최단거리를 제외한 나머지를 다 더해준다.
		for (j = 0; j < n; j++) {
			if (i != j) {
				result = result + dist[i][j];
			}
		}
	}

	printf("%.3f", result / (n * (n - 1)));    // 총 개수로 나눠준다.

	return 0;
}

이렇게 쉬운 알고리즘을 두고 Time Limit으로 고생하였다고 한다..