Seren dev's blog
article thumbnail

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

 

1719번: 택배

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하

www.acmicpc.net

1. 풀이

한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 구해야 하기 때문에

그래프 최단거리 알고리즘(다익스트라)을 응용하여 풀었다.

 

다익스트라 알고리즘을 진행할 때, 각 엣지에 먼저 거치는 정점도 저장하기 위해

Edge 클래스에 int형 멤버변수 startV를 추가했고, 이후 PQ에 엣지를 추가할 때 이전 엣지의 startV를 세팅하여 저장하는 로직을 추가하였다.

<java />
static class Edge implements Comparable<Edge> { int v; int cost; int startV; public Edge(int v, int cost) { this.v = v; this.cost = cost; startV = 0; } public Edge(int v, int cost, int startV) { this.v = v; this.cost = cost; this.startV = startV; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } } static int[][] routeChart; // 가장 먼저 거치는 정점을 저장하는 경로표 static ArrayList<ArrayList<Edge>> graph = new ArrayList<>(); // 인접리스트 ... static void dijkstra(int source) { int[] dist = new int[n+1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[source] = 0; PriorityQueue<Edge> pq = new PriorityQueue<>(); pq.add(new Edge(source, 0)); while(!pq.isEmpty()) { Edge cur = pq.poll(); if (cur.cost > dist[cur.v]) continue; routeChart[source][cur.v] = cur.startV; // 경로표에 저장 for (Edge next: graph.get(cur.v)) { if (dist[next.v] > cur.cost + next.cost) { dist[next.v] = cur.cost + next.cost; if (cur.cost == 0) { // next.v가 출발지 다음 정점인 경우 pq.add(new Edge(next.v, dist[next.v], next.v)); } else { // cur.startV를 새로 추가하려는 Edge의 startV로 세팅하여 PQ에 추가 pq.add(new Edge(next.v, dist[next.v], cur.startV)); } } } } }

 

모든 정점에 대해 각 정점을 시작으로 하는 다익스트라를 실행하여,  한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 저장한 경로표를 출력한다.

 

2. 코드

<java />
import java.io.*; import java.util.*; public class Main { static class Edge implements Comparable<Edge> { int v; int cost; int startV; public Edge(int v, int cost) { this.v = v; this.cost = cost; startV = 0; } public Edge(int v, int cost, int startV) { this.v = v; this.cost = cost; this.startV = startV; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } } static int n, m; static ArrayList<ArrayList<Edge>> graph = new ArrayList<>(); // 인접리스트 static int[][] routeChart; // 가장 먼저 거치는 정점을 저장하는 경로표 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); // 초기화 n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } routeChart = new int[n+1][n+1]; // 그래프 정보 입력 받기 for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); graph.get(a).add(new Edge(b, cost)); graph.get(b).add(new Edge(a, cost)); } // 모든 정점에 대해, 각 정점을 시작으로 하는 다익스트라 실행 for (int i = 1; i <= n; i++) { dijkstra(i); } print(); } static void dijkstra(int source) { int[] dist = new int[n+1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[source] = 0; PriorityQueue<Edge> pq = new PriorityQueue<>(); pq.add(new Edge(source, 0)); while(!pq.isEmpty()) { Edge cur = pq.poll(); if (cur.cost > dist[cur.v]) continue; routeChart[source][cur.v] = cur.startV; // 경로표에 저장 for (Edge next: graph.get(cur.v)) { if (dist[next.v] > cur.cost + next.cost) { dist[next.v] = cur.cost + next.cost; if (cur.cost == 0) { // next.v가 출발지 다음 정점인 경우 pq.add(new Edge(next.v, dist[next.v], next.v)); } else { // cur.startV를 새로 추가하려는 Edge의 startV로 세팅하여 PQ에 추가 pq.add(new Edge(next.v, dist[next.v], cur.startV)); } } } } } static void print() { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { sb.append("- "); } else { sb.append(routeChart[i][j] + " "); } } sb.append("\n"); } System.out.println(sb); } }

 

3. 다른 풀이

3.1. 다익스트라 활용

start -> next.v로 가는 최단거리를 찾은 경우, 반대로 route[next.v][start] = cur.v를 찾는다.

Edge 클래스에 startV 멤버변수를 추가할 필요 없이, 기존 다익스트라 코드에 위의 한 줄만 추가하면 된다.

<java />
import java.io.*; import java.util.*; public class Main { static class Edge implements Comparable<Edge> { int v; int cost; public Edge(int v, int cost) { this.v = v; this.cost = cost; } @Override public int compareTo(Edge o) { return this.cost - o.cost; } } static int n, m; static ArrayList<ArrayList<Edge>> graph = new ArrayList<>(); // 인접리스트 static int[][] routeChart; // 가장 먼저 거치는 정점을 저장하는 경로표 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); // 초기화 n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } routeChart = new int[n+1][n+1]; // 그래프 정보 입력 받기 for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); graph.get(a).add(new Edge(b, cost)); graph.get(b).add(new Edge(a, cost)); } // 모든 정점에 대해, 각 정점을 시작으로 하는 다익스트라 실행 for (int i = 1; i <= n; i++) { dijkstra(i); } print(); } static void dijkstra(int source) { int[] dist = new int[n+1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[source] = 0; PriorityQueue<Edge> pq = new PriorityQueue<>(); pq.add(new Edge(source, 0)); while(!pq.isEmpty()) { Edge cur = pq.poll(); if (cur.cost > dist[cur.v]) continue; for (Edge next: graph.get(cur.v)) { if (dist[next.v] > cur.cost + next.cost) { dist[next.v] = cur.cost + next.cost; pq.add(new Edge(next.v, dist[next.v])); routeChart[next.v][source] = cur.v; // 중요! } } } } static void print() { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { sb.append("- "); } else { sb.append(routeChart[i][j] + " "); } } sb.append("\n"); } System.out.println(sb); } }

 

3.2. 플로이드 활용

N <= 200이므로 시간복잡도가 O(N^3)인 플로이드 알고리즘을 사용할 수 있다.

주의할 점

최소거리를 저장하는 dist 배열을 초기화할 때 Intger.MAX_VALUE 값으로 하지 말아야 한다.

Integer.MAX_VALUE로 하면 비교하는 과정에서 범위를 넘어서 음수 값이 되어버리기 때문이다.

<java />
static void floyd() { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; routeChart[i][j] = routeChart[i][k]; // 경로표 저장 } } } } }

3.2.1. 전체 코드

<java />
import java.io.*; import java.util.*; public class Main { static int n, m; static int[][] dist; static int[][] routeChart; // 가장 먼저 거치는 정점을 저장하는 경로표 static final int MAX = 200 * 10000; // 중요! public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); // 초기화 n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); dist = new int[n+1][n+1]; routeChart = new int[n+1][n+1]; for (int i = 1; i <= n; i++) { Arrays.fill(dist[i], MAX); dist[i][i] = 0; } // 그래프 정보 입력 받기 for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); dist[a][b] = cost; dist[b][a] = cost; routeChart[a][b] = b; routeChart[b][a] = a; } // 플로이드 floyd(); print(); } static void floyd() { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; routeChart[i][j] = routeChart[i][k]; } } } } } static void print() { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { sb.append("- "); } else { sb.append(routeChart[i][j] + " "); } } sb.append("\n"); } System.out.println(sb); } }

 

 

728x90
profile

Seren dev's blog

@Seren dev

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!