sw expert academy 1263번 사람 네트워크2 자바(java) 풀이
문제정리
- Closeness Centrality(CC) : 네트워크 상에서 한 사용자가 다른 모든 사람에게 얼마나 가까운가?
- 사용자 i의 CC(i)는 다음과 같이 계산한다.
모든 dist(i,j)의 합 (단 dist(i,j)는 노드 i로부터 노드 j까지의 최단 거리)
- N은 1000 이하이다.
- 사람들의 CC 값중 최소값을 출력하여라.
문제 풀이
모든 노드에서의 최단 경로를 구하여야 합니다. 즉 All pairs shortest path problem이 됩니다
이는 플로이드-워셜 알고리즘을 이용하여 구할 수 있습니다.
1. 플로이드 워셜 알고리즘
한 정점에서 모든 정점으로 가는 최단 경로를 구합니다. O(n^3) 알고리즘 이지만 코드가 간단하기 때문에 때에따라 잘 쓰면 좋습니다.
3중 for 문만을 이용하면 구할 수 있습니다.
첫번째 for문은 중간에 거쳐가는 정점
두번째 for문은 시작 정점
세번째 for문은 도착 정점을 관리 합니다.
1번 정점에서 3번 정점으로 갈때 다른 정점을 거쳐서 가는 것이 더 빠를 수 있습니다. 이런 경우를 찾아서 업데이트 해줍니다.
예를 들어 1번 정점에서 다른 정점으로 가는 최단 경로가 다음과 같이 구해집니다.
그러므로 CC(i)는 다음과 같이 모두 더하여 구할 수 있습니다.
0 1 1 2 2
1->1 : 없음
1->2 : 1이 최단거리
1->3 : 1이 최단거리
1->4 : 2가 최단거리
1->5 : 2가 최단거리
=> 0 + 1 + 1 + 2 + 2 = 6
모든 점에 대해서 합을 구하고, 그 중에서 제일 작은 값을 구하면 됩니다.
2. 다익스트라 알고리즘
플로이드 워셜은 모든 점에 대해서 구하지만 다익스트라는 한 점에 대해서 다른 점 까지의 최단 거리를 구할 수 있습니다.
즉 이 알고리즘을 모든 점에 대하여 적용하면 모든 점에서 다른 점들에 대한 최단거리 들을 구할 수 있습니다.
다익스트라 알고리즘을 n번 수행하여 나온 값들 중 제일 작은 값을 구하면 됩니다.
swea 사람 네트워크2 플로이드 워셜 알고리즘 자바 코드
swea 사람 네트워크2 다익스트라 알고리즘 자바 코드