문제 설명
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
내 답
플로이드 워셜 알고리즘을 생각해봤지만,
시간 복잡도가 O(N^3)이고, 문제에서의 N 범위는 최대 1000이기 때문에,
해당 문제에서는 비효율적일 것이라 판단했고,
다익스트라를 사용하기로 결정하여 다익스트라 알고리즘으로 풀어냈다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static class Node implements Comparable<Node>{
int v, w;
public Node() {
}
@Override
public String toString() {
return "Node [v=" + v + ", w=" + w + "]";
}
public Node(int v, int w) {
super();
this.v = v;
this.w = w;
}
@Override
public int compareTo(Node o) {
return this.w - o.w;
}
}
static int N, M, X, max;
static ArrayList<Node>[] adjList;
static int[] dist;
static boolean[] visited;
public static void main(String[] args) {
init();
for (int i=1; i<=N; i++) {
int tmp1 = dijkstra(i, X);
int tmp2 = dijkstra(X, i);
max = Math.max(max, tmp1+tmp2);
// System.out.println(i+" -> "+ X + " = " + (tmp1+tmp2));
}
System.out.println(max);
}
private static int dijkstra(int start, int end) {
int res = 0;
dist = new int[N+1];
Arrays.fill(dist, Integer.MAX_VALUE);
visited = new boolean[N+1];
PriorityQueue<Node> pq = new PriorityQueue<>();
dist[start] = 0; // 시작점은 거리 0
pq.add(new Node(start, 0));
while(!pq.isEmpty()) {
Node curr = pq.poll(); // 큐에서 현제 노드 뽑음
if (curr.v == end) {
return dist[curr.v];
}
if (visited[curr.v]) continue;
visited[curr.v] = true;
// 인접 노드 탐색
for (Node node : adjList[curr.v]) {
// 아직 방문 안했고, 거리가 더 작으면 갱신
if (!visited[node.v] && dist[node.v] > dist[curr.v] + node.w) {
dist[node.v] = dist[curr.v] + node.w;
pq.add(new Node(node.v, dist[node.v]));
}
}
// if (visited[end]) {
// System.out.println(Arrays.toString(dist));
// return dist[end];
// }
}
return dist[end];
}
private static void init() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
X = sc.nextInt();
adjList = new ArrayList[N+1];
for (int i=1; i<=N; i++) {
adjList[i] = new ArrayList<>();
}
for (int i=0; i<M; i++) {
adjList[sc.nextInt()].add(new Node(sc.nextInt(), sc.nextInt()));
}
max = 0;
}
}
다익스트라 문제를 여러번 풀었지만, 우선순위 큐를 사용하고, Node 객체를 만들어 푸는
방식의 다익스트라 구현은 계속 헷갈린다.
플로이드 워셜 알고리즘도 간단해 보이는데 생각보다 머리에 잘 들어오지 않는다.
계속해서 풀어봐야겠다!
보완점
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static class Node implements Comparable<Node> {
int v, w;
public Node(int v, int w) {
this.v = v;
this.w = w;
}
@Override
public int compareTo(Node o) {
return this.w - o.w;
}
}
static int N, M, X;
static ArrayList<Node>[] adjList;
static int[] distFromX, distToX; // X로부터의 거리, X로 가는 거리 배열
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
init();
// X에서 모든 노드로 가는 최단 거리 계산
distFromX = dijkstra(X);
int maxDist = 0;
// 각 노드에서 X로 가는 최단 거리 계산 후 최대값 찾기
for (int i = 1; i <= N; i++) {
if (i != X) { // X에서 X로 가는 경로는 제외
distToX = dijkstra(i); // i에서 출발해 X로 가는 거리 배열
maxDist = Math.max(maxDist, distToX[X] + distFromX[i]);
}
}
System.out.println(maxDist);
}
// 다익스트라 메서드: 시작 노드로부터 각 노드까지의 최단 거리 계산
private static int[] dijkstra(int start) {
int[] dist = new int[N + 1];
Arrays.fill(dist, INF);
PriorityQueue<Node> pq = new PriorityQueue<>();
dist[start] = 0;
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
Node curr = pq.poll();
// 현재 노드로부터 인접 노드 탐색
for (Node next : adjList[curr.v]) {
if (dist[next.v] > dist[curr.v] + next.w) {
dist[next.v] = dist[curr.v] + next.w;
pq.add(new Node(next.v, dist[next.v]));
}
}
}
return dist;
}
// 입력 및 초기화 메서드
private static void init() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
X = sc.nextInt();
adjList = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adjList[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
adjList[u].add(new Node(v, w));
}
sc.close();
}
}
1. 모든 경우에 i부터 X, X부터 i 두번 다익스트라를 사용했는데,
X애서 i로 가는 최단경로를 미리 한번에 구한 후, i부터 X로 가는 최단거리만 계산하는 방식으로 연산량을 줄임
2. 방문 배열을 제거해도 구동에 문제가 없어 방문 배열을 제거함