https://www.acmicpc.net/problem/1719
1719번: 택배
명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하
www.acmicpc.net
풀이
한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 구해야 하기 때문에
그래프 최단거리 알고리즘(다익스트라)을 응용하여 풀었다.
다익스트라 알고리즘을 진행할 때, 각 엣지에 먼저 거치는 정점도 저장하기 위해
Edge 클래스에 int형 멤버변수 startV를 추가했고, 이후 PQ에 엣지를 추가할 때 이전 엣지의 startV를 세팅하여 저장하는 로직을 추가하였다.
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));
}
}
}
}
}
모든 정점에 대해 각 정점을 시작으로 하는 다익스트라를 실행하여, 한 정점에서 다른 정점으로 최단경로로 이동할 때 가장 먼저 거쳐야 하는 정점을 저장한 경로표를 출력한다.
코드
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);
}
}
다른 풀이
다익스트라 활용
start -> next.v로 가는 최단거리를 찾은 경우, 반대로 route[next.v][start] = cur.v를 찾는다.
Edge 클래스에 startV 멤버변수를 추가할 필요 없이, 기존 다익스트라 코드에 위의 한 줄만 추가하면 된다.
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);
}
}
플로이드 활용
N <= 200이므로 시간복잡도가 O(N^3)인 플로이드 알고리즘을 사용할 수 있다.
주의할 점
최소거리를 저장하는 dist 배열을 초기화할 때 Intger.MAX_VALUE 값으로 하지 말아야 한다.
Integer.MAX_VALUE로 하면 비교하는 과정에서 범위를 넘어서 음수 값이 되어버리기 때문이다.
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]; // 경로표 저장
}
}
}
}
}전체 코드
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
'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글
| [백준] 9079번 : 동전 게임 - 자바[Java] (0) | 2024.03.09 |
|---|---|
| [백준] 14938번 : 서강그라운드 - 자바[Java] (0) | 2024.02.02 |
| [백준] 14940번 : 쉬운 최단거리 - 자바[Java] (0) | 2024.01.30 |
| [백준] 16973번 : 직사각형 탈출 - 자바[Java] (0) | 2024.01.15 |
| [백준] 17836번 : 공주님을 구해라! - 자바[Java] (1) | 2024.01.10 |
