[SWEA] 1263 사람 네트워크2 (D6 / 플로이드 워셜) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN&categoryId=AV18P2B6Iu8CFAZN&categoryType=CODE&problemTitle=%EC%82%AC%EB%9E%8C+%EB%84%A4%ED%8A%B8&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제 해석

여러 사람들 중 영향력이 가장 큰 사람 구하기
영향력이 큰 사람 == CC(i)가 가장 작은 사람
CC(i) : 사람 i와 다른 사람들간의 최단거리를 모두 합한 것


- 입력
첫 번째 요소 : N # 사람 수
나머지 요소 : 인접행렬의 데이터가 주어짐 

3 0 1 0 1 0 1 0 1 0
->
3 
0 1 0 
1 0 1 
0 1 0


- 출력
CC(i)의 최소값 출력

 

 

코드

import java.io.*;
import java.util.*;

public class 사람네트워크 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int test_case = 1; test_case <= T; test_case++) {
			int answer = Integer.MAX_VALUE;

			// 한줄에 모두 입력
			st = new StringTokenizer(br.readLine());

			// 첫 번째 인자 (인원 수)
			int n = Integer.parseInt(st.nextToken());
			int INF = 99999999;

			int[][] map = new int[n][n];

			// 나머지 인자 (인접 행렬)
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] == 0) {
						map[i][j] = INF;
					}
				}
			}

			// 플로이드 워셜 : 경출도
			for (int k = 0; k < n; k++) { // 경유
				for (int i = 0; i < n; i++) { // 출발
					// 경우-출발이 동일한 경우 pass
					if (k == i)
						continue;
					for (int j = 0; j < n; j++) { // 도착
						// 출발-도착, 경유-도착이 동일한 경우 pass
						if (i == j || j == k)
							continue;

						if (map[i][j] > map[i][k] + map[k][j]) {
							map[i][j] = map[i][k] + map[k][j];
						}
					}
				}
			}

			int[] cc = new int[n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j] != INF) {
						cc[i] += map[i][j];
					}
				}
				if (cc[i] < answer) {
					answer = cc[i];
				}
			}

			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}
}

 

 

 

코드 해석

bfs, 다익스트라, 플로이드 워셜로 풀 수 있는 문제입니다.

문제에 설명이 조금 난해할 뿐 해석만 하면 모든 정점의 최단거리를 구하는 플로이드 워셜의 기본적인 문제입니다.


제공하는 테스트 케이스에서는 인접행렬로 데이터를 제공하고, 0과 1로 이뤄져있습니다.
 
따라서 모든 간선의 값(비용)이 1이라고 가정하고, 각 사람들이 다른 모든 간선까지 가는 최소 비용을 구하면 됩니다.

 

각 사람의 구해진 최단거리를 모두 합산 한 후 최소 값을 출력하면 됩니다.

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice