[SWEA 1263] 사람 네트워크2 (Dijkstra, Floyd-Warshall)(JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN

SW Expert Academy

1. 주의할 점

- 이 문제는 Test가 불가능하므로 제출을 통해 검사해야 한다

- 다익스트라 알고리즘 혹은 플로이드-와샬 알고리즘을 통해 구현할 수 있다

- 테스트 케이스마다 초기화를 해야한다

 

2. 구현

[다익스트라 알고리즘]

- 2차 배열에 간선의 정보를 저장해도 되지만, 시간이 많이 소요되므로 List형태로 간선의 정보를 저장한다

- 모든 정점에서부터 시작해 각 정점까지의 거리를 우선순위큐를 사용하여 구한다

- 계산이 끝나면 각 정점까지의 거리를 모두 더한 후, 결과값가 비교한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution_d6_1263_사람네트워크2 {
	static class Info implements Comparable<Info>{
		int idx,val;
		public Info(int idx,int val) {
			this.idx=idx;
			this.val=val;
		}
		@Override
		public int compareTo(Info o) {
			return Integer.compare(this.val, o.val);
		}
	}
	static int arr[][];
	static int dist[];
	static boolean visit[];
	static List<Info> li[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for(int t=1;t<=test;t++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			int num = Integer.parseInt(st.nextToken());
			int result = Integer.MAX_VALUE;
			//초기화
			//arr = new int[num][num];
			li = new List[num];
			for(int i=0;i<num;i++)
				li[i]=new ArrayList<>();
			
			for(int i=0;i<num;i++) {
				for(int j=0;j<num;j++) {
					int val =Integer.parseInt(st.nextToken());
					//arr[i][j]=val;
					if(val==1)
						li[i].add(new Info(j,1));
				}
			}
			
			for(int i=0;i<num;i++) {
				dist = new int[num];
				for(int j=0;j<num;j++)
					dist[j]=Integer.MAX_VALUE;
				visit = new boolean[num];
				dist[i]=0;
				PriorityQueue<Info> pq = new PriorityQueue<>();
				pq.offer(new Info(i,0));
				Info ii;
				
				while(!pq.isEmpty()) {
					ii = pq.poll();
					int cidx = ii.idx;
					int cv = ii.val;
					if(visit[cidx]) continue;
					visit[cidx]=true;
					for(int j=0;j<li[cidx].size();j++) {
						int next = li[cidx].get(j).idx;
						int nv = li[cidx].get(j).val;
						if(dist[next]>cv+nv) {
							dist[next]=cv+nv;
							pq.offer(new Info(next,nv+cv));
						}
					}
				}
				int cnt=0;
				for(int j=0;j<num;j++)
					cnt+=dist[j];
				result = Math.min(result, cnt);
			}
			System.out.println("#"+t+" "+result);
		}
	}
}

 

[플로이드-와샬 알고리즘]

- 2차원 배열을 사용한다

- 배열의 값을 입력받을 때, 0을 입력받으며(간선이 존재X) i!=j인 경우(자기 자신으로 돌아가는 경우) 높은 값을 부여한다 (단, Integer.MAX_VALUE를 부여하면 2개를 더했을 때 음수값이 나오므로 그보다 작은 수를 등록한다)

- A->B로 가는 경우, A->C->B로 가는 경우와 비교하면서 최소값을 갱신한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution_d6_1263_사람네트워크2_floyd {
	static int arr[][];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for(int t=1;t<=test;t++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			int num = Integer.parseInt(st.nextToken());
			int result = Integer.MAX_VALUE;
			//초기화
			arr = new int[num][num];
			
			for(int i=0;i<num;i++) {
				for(int j=0;j<num;j++) {
					int val =Integer.parseInt(st.nextToken());
					arr[i][j]=val;
					if(arr[i][j]==0 && i!=j)
						arr[i][j]=987654321;
				}
			}
			for(int k=0;k<num;k++) 
				for(int i=0;i<num;i++) 
					for(int j=0;j<num;j++) 
						arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
			for(int k=0;k<num;k++) {
				int temp=0;
				for(int i=0;i<num;i++) 
					temp+=arr[k][i];
				result = Math.min(result,temp);
			}
			System.out.println("#"+t+" "+result);
		}
	}
}