[JAVA]백준_1719_택배

문제 : https://www.acmicpc.net/problem/1719

1719번: 택배

문제 유형 : 다익스트라, 그래프 이론

 

풀이 방식 

(1) 다익스트라는 한 정점에서 다른 모든 정점을 찾을 때 사용

     => 최단 경로의 최근 노드를 저장하여 dfs로 제일먼저 가야할 노드를 찾음

(2) 플로이드 와샬은 모든 최단 경로를 구하는 방법에 사용됨 

     => 최근 노드를 저장. 양방향 그래프이므로 최근경로를 거꾸로 뒤집으면 처음 가야할 노드를 찾을 수있음

 

소스코드1 (다익스트라)

package BOJ;

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

// 다익스트라
public class BOJ_1719_택배_Main {

	private static int[] path;
	private static int[] value;
	private static List<int[]>[] list;
	private static StringBuilder sb;
	private static boolean[] visited;
	private static int n;
	
	public static void main(String[] args) throws IOException {
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken()); // 집하장간 경로의 개수
		list = new ArrayList[n+1];
		for (int i = 1; i < n+1; i++) {
			list[i] = new ArrayList<int[]>();
		}
		
		// 2. 구현
		// 2-1. 인접 리스트
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			list[from].add(new int[] {to, val});
			list[to].add(new int[] {from, val});
		}
		
		// 2-2. 다익스트라
		sb = new StringBuilder();
		for (int i = 1; i < n+1; i++) {
			path = new int[n+1];
			value = new int[n+1];
			visited = new boolean[n+1];
			Arrays.fill(value, Integer.MAX_VALUE);
			dijkstra(i);
		}
		System.out.println(sb.toString());
	}

	private static void dijkstra(int num) {
		int start = num;
		value[num] = 0;
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		pq.offer(new int[] {start, 0});
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			int cur_num = cur[0];
			if(!visited[cur_num]) {
				visited[cur_num] = true;
				for (int i = 0; i < list[cur_num].size(); i++) {
					int[] next = list[cur_num].get(i);
					int next_num = next[0];
					int next_val = next[1];
					if(value[next_num]>value[cur_num]+next_val) {
						path[next_num] = cur_num;
						value[next_num] = value[cur_num]+next_val;
						pq.offer(new int[] {next_num, value[next_num],next_num});
					}
				}
			}
		}
		
		// 2-3. dfs로 추적하기
		for (int i = 1; i < n+1; i++) {
			if(i==num) sb.append("- ");
			else {
				int ans = find(i, num);
				sb.append(ans+" ");
			}
		}
		sb.append("\n");
	}

	private static int find(int i, int start) {
		if(path[i] == start) return i;
		return find(path[i], start);
	}

	
}

 

소스코드2 (플로이드와샬)

package BOJ;

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

// 플로이드 와샬
public class BOJ_1719_택배_Main2 {

	public static void main(String[] args) throws IOException {
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken()); // 집하장간 경로의 개수
		int[][] matrix = new int[n+1][n+1];
		int[][] path = new int[n+1][n+1];
		for (int i = 1; i < n+1; i++) {
			Arrays.fill(matrix[i], 10001);
			matrix[i][i]=0;
		}
		
		// 2. 구현
		// 2-1. 인접 행렬
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			matrix[to][from] = val;
			matrix[from][to] = val;
			
			path[from][to] = from;
			path[to][from] = to;
		}
		
		// 2-2. 플로이드 와샬
		for (int k = 1; k < n+1; k++) {         // 경로
			for (int i = 1; i < n+1; i++) {     // 출발
				for (int j = 1; j < n+1; j++) { // 도착
					if(matrix[i][j]>matrix[i][k]+matrix[k][j]) {
						matrix[i][j] = matrix[i][k] + matrix[k][j]; // 최단 경로 갱신
						path[i][j] = path[k][j]; // i에서 j까지 => k를 지나 j까지
					}
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < n+1; j++) {
				if(i==j) sb.append("- ");
				else sb.append(path[j][i]+" ");
			}sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}

}