백준 31230번: 모비스터디 Java Solution
1. Problem Definition & Ananlysis
개의 정점과 개의 간선으로 구성된 그래프에서 번 정점부터 번 정점 간의 최단 거리를 형성하는 정점들의 목록을 오름차순으로 정리하는 문제이다. 주의해야 할 것은 최단 거리를 갖는 경로가 여러 개일 수 있다는 점이다.
문제 해결을 위해 크게 두 가지 과정이 필요하다.
- 다익스트라 알고리즘을 기반으로 번 정점에서 번 정점에 이르는 최단 거리를 찾고 역추적 데이터를 생성한다.
- 역추적 데이터를 기반으로 최단 거리를 형성하는 정점들을 찾고 정렬한다.
2. Solution
흐름을 파악하기 쉽게 하기 위해 기존에 작성한 코드를 리팩터링했다. 리팩터링한 코드 역시 시간 초과 없이 아슬아슬하게 통과하는 것을 확인했다.
import java.io.*;
import java.util.*;
public class Main {
static class Edge implements Comparable<Edge> {
int src, dest;
long cost;
public Edge(int src, int dest, long cost) {
this.src = src;
this.dest = dest;
this.cost = cost;
}
public int getSrc() {
return src;
}
public int getDest() {
return dest;
}
public long getCost() {
return cost;
}
public int compareTo(Edge other) {
return Long.compare(cost, other.cost);
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static final long INF = Long.MAX_VALUE;
static int N, M, A, B;
static List<List<Edge>> graph = new ArrayList<>();
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
for (int i = 0; i <= N; i++)
graph.add(new ArrayList<>());
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
int src = Integer.parseInt(st.nextToken());
int dest = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(src).add(new Edge(src, dest, cost));
graph.get(dest).add(new Edge(dest, src, cost));
}
Map<Integer, List<Integer>> parents = dijkstra();
List<Integer> result = findShortestPathNodes(parents);
sb.append(result.size()).append('\n');
for (int node : result)
sb.append(node).append(' ');
System.out.println(sb.toString());
}
public static Map<Integer, List<Integer>> dijkstra() {
long[] distance = new long[N + 1];
Map<Integer, List<Integer>> parents = new HashMap<>();
Arrays.fill(distance, INF);
PriorityQueue<Edge> pq = new PriorityQueue<>();
distance[A] = 0;
pq.offer(new Edge(A, A, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int src = edge.getSrc(), mid = edge.getDest();
long midCost = edge.getCost();
if (distance[mid] < midCost)
continue;
for (Edge nextEdge : graph.get(mid)) {
int dest = nextEdge.getDest();
long destCost = nextEdge.getCost();
if (midCost + destCost < distance[dest]) {
distance[dest] = midCost + destCost;
parents.put(dest, new ArrayList<>());
parents.get(dest).add(mid);
pq.offer(new Edge(src, dest, distance[dest]));
} else if (midCost + destCost == distance[dest]) {
parents.put(dest, parents.getOrDefault(dest, new ArrayList<>()));
parents.get(dest).add(mid);
}
}
}
return parents;
}
public static List<Integer> findShortestPathNodes(Map<Integer, List<Integer>> parents) {
List<Integer> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
Queue<Integer> queue = new ArrayDeque<>();
set.add(B);
queue.offer(B);
list.add(B);
while (!queue.isEmpty()) {
int curr = queue.poll();
if (curr == A) {
continue;
}
for (int parent : parents.get(curr))
if (!set.contains(parent)) {
set.add(parent);
queue.add(parent);
list.add(parent);
}
}
Collections.sort(list);
return list;
}
}2-1. 다익스트라 알고리즘 수행
public static Map<Integer, List<Integer>> dijkstra() {
long[] distance = new long[N + 1];
Map<Integer, List<Integer>> parents = new HashMap<>();
Arrays.fill(distance, INF);
PriorityQueue<Edge> pq = new PriorityQueue<>();
distance[A] = 0;
pq.offer(new Edge(A, A, 0));
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int src = edge.getSrc(), mid = edge.getDest();
long midCost = edge.getCost();
if (distance[mid] < midCost)
continue;
for (Edge nextEdge : graph.get(mid)) {
int dest = nextEdge.getDest();
long destCost = nextEdge.getCost();
if (midCost + destCost < distance[dest]) {
distance[dest] = midCost + destCost;
parents.put(dest, new ArrayList<>());
parents.get(dest).add(mid);
pq.offer(new Edge(src, dest, distance[dest]));
} else if (midCost + destCost == distance[dest]) {
parents.put(dest, parents.getOrDefault(dest, new ArrayList<>()));
parents.get(dest).add(mid);
}
}
}
return parents;
}다익스트라 알고리즘을 수행하면서 역추적 데이터를 함께 저장한다. 이때 앞서 설명한 것과 같이 최단 거리를 갖는 경로가 여러 개일 수 있기 때문에 Map의 키는 어떤 정점, 값은 그 정점의 부모 집합으로 정의했다.
if (midCost + destCost < distance[dest]) {
distance[dest] = midCost + destCost;
parents.put(dest, new ArrayList<>());
parents.get(dest).add(mid);
pq.offer(new Edge(src, dest, distance[dest]));
} else if (midCost + destCost == distance[dest]) {
parents.put(dest, parents.getOrDefault(dest, new ArrayList<>()));
parents.get(dest).add(mid);
}핵심은 위 코드 블럭이다.
- 만약 새로운 최단 거리를 갱신했다면, 기존의 부모 집합은 최단 거리 경로에 포함되지 않으므로 새로운 List 객체를 생성한다.
- 만약 기존의 최단 거리와 똑같은 거리를 갖는 경로를 찾았다면, 기존의 부모 집합에 새로운 부모를 추가한다.
2-2. 역추적 데이터를 기반으로 최단 거리를 형성하는 정점 탐색
public static List<Integer> findShortestPathNodes(Map<Integer, List<Integer>> parents) {
List<Integer> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
Queue<Integer> queue = new ArrayDeque<>();
set.add(B);
queue.offer(B);
list.add(B);
while (!queue.isEmpty()) {
int curr = queue.poll();
if (curr == A) {
continue;
}
for (int parent : parents.get(curr))
if (!set.contains(parent)) {
set.add(parent);
queue.add(parent);
list.add(parent);
}
}
Collections.sort(list);
return list;
}다음으로는 앞서 형성한 역추적 데이터를 기반으로 BFS 알고리즘을 수행해 최단 거리를 갖는 경로상에 있는 모든 정점을 찾는다.
위 예시 그래프를 보면서 번 정점에서 번 정점으로 BFS를 수행할 때 아래와 같은 조건문을 삽입한 이유가 무엇인지 생각해 보자.
if (curr == A) {
continue;
}~ 간의 최단 거리를 갖는 각 경로에 포함된 정점의 개수는 다를 수 있다. 그렇기 때문에 번 정점을 찾았더라도 BFS 루프를 즉시 종료할 수 없다. 번 정점을 찾았을 때 expanding을 중단하고 다시 기존에 추가되었던 정점들의 부모 집합을 탐색해 나가는 것이 핵심이다.
3. Conclusion
언어에 따른 유불리가 있는 듯하다. C++로 작성하면 시간 초과에 쉽게 안 걸렸을 것 같은데, Java를 사용하니 시간 초과가 발생하는 경우가 있어 코드 최적화가 필요했다.
그리고 문제 설명이 명확해서 골드 3으로 평가되어 있는 것 같다. 같은 골드 3 문제들에 비해 난이도가 높은 편이라고 생각된다.
안녕하세요