[정올][최단거리] 1108 페이지 전환

각 노드에서 자신을 제외한 노드로 이동하는 최단거리를 구하여 모두 더하는 문제이다. 

BFS를 이용하여 문제를 해결할 수 있다. 

	package sdk.algo.shortdist;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	/**
	* 정올, 알고리즘, 최단거리, 1108
	* 페이지 전환
	*
	* @author whitebeard-k
	*
	*/
	public class Problem1108 {
	public static int bfs(Queue<Integer> queue, int[][] array, int[] visited, int target, int moveCount) {
	int size = queue.size();
	while (size-- > 0) {
	int loc = queue.poll();
	if (loc == target)
	return moveCount;
	else {
	for (int i = 0; i < array.length; i++) {
	if (loc != i && visited[i] != 1 && array[loc][i] == 1) {
	visited[i] = 1;
	queue.add(i);
	}
	}
	}
	}
	return bfs(queue, array, visited, target, ++moveCount);
	}
	public static void main(String[] args) {
	// int n = 5;
	// int[][] inputs = {{ 1 ,2 },
	// { 2 ,4 },
	// { 1 ,3 },
	// { 3 ,1 },
	// { 4 ,3 }};
	// int max = 4;
	int max = Integer.MIN_VALUE;
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[][] inputs = new int[n][2];
	for (int i = 0; i < n; i++) {
	inputs[i][0] = sc.nextInt();
	inputs[i][1] = sc.nextInt();
	max = (inputs[i][0] > max) ? inputs[i][0] : max;
	max = (inputs[i][1] > max) ? inputs[i][1] : max;
	}
	sc.close();
	int[][] array = new int[max + 1][max + 1];
	for (int i = 0; i < n; i++) {
	array[inputs[i][0]][inputs[i][1]] = 1;
	}
	Queue<Integer> queue = new LinkedList<>();
	float sum = 0;
	float count = 0;
	for (int start = 1; start < n; start++) {
	for (int i = 1; i < n; i++) {
	if (start == i)
	continue;
	queue.clear();
	queue.add(start);
	int[] visited = new int[max+1];
	visited[start] = 1;
	int result = bfs(queue, array, visited, i, 0);
	sum += result;
	count++;
	}
	}
	System.out.printf("%.3f", sum / count);
	}
	}

view raw Problem1108.java hosted with ❤ by GitHub

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=388&sca=50&sfl=wr_hit&stx=1108&sop=and