[백준 11779] 최소비용 구하기2 (JAVA)
🔰 문제
💡 접근방식
다익스트라에 경로 역추적까지 해야하는 문제
다익스트라는 인접리스트와 PriorityQueue를 사용하여 구현.
이때 경로 역추적을 위해 현재 도시 기준으로 방문한 이전 도시를 저장해주는 preCity 배열 선언
경로 역추적은 preCity[end]에서부터 stack을 이용하여 역추적한다.
💦 풀면서 실수, 놓친 점
다익스트라 식에서
if (d[cur] < curCity.weight)
continue;
위에 한줄 안 넣어서 시간초과 났다.
그리고 오랜만에 다익스트라 풀어서인지 식도 잘 기억이 안 났다.. 다시 복습하자!!
🕑 소요시간
45분
💻 풀이
import java.io.*;
import java.util.*;
// BOJ / 최소비용 구하기2 / G3 / 45분
// https://www.acmicpc.net/problem/11779
public class Main_11779 {
static class City implements Comparable<City> {
int to;
int weight;
public City(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(City o) { // 비용 오름차순 정렬
return this.weight - o.weight;
}
}
static int N, M;
static int d[], preCity[];
static int start, end;
static List<ArrayList<City>> graph;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
d = new int[N + 1]; // 해당 도시까지 가는데의 최소 비용
preCity = new int[N + 1]; // 이전도시
Arrays.fill(d, Integer.MAX_VALUE);
graph = new ArrayList<>();
for (int i = 0; i < N + 1; i++)
graph.add(new ArrayList<City>());
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
graph.get(from).add(new City(to, weight));
}
StringTokenizer st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
dijkstra(start);
System.out.println(d[end]); // 최단 거리
// 경로 역추적
int cnt = 0;
Stack<Integer> stack = new Stack<>();
stack.push(end);
while (preCity[end] != 0) {
cnt += 1;
stack.push(preCity[end]);
end = preCity[end];
}
System.out.println(cnt + 1);
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
private static void dijkstra(int start) {
PriorityQueue<City> pq = new PriorityQueue<City>();
pq.add(new City(start, 0));
d[start] = 0;
while (!pq.isEmpty()) {
City curCity = pq.poll();
int cur = curCity.to;
if (d[cur] < curCity.weight)
continue;
for (City next : graph.get(cur)) {
if (d[next.to] > d[cur] + next.weight) { // 최단거리 cost 업데이트
d[next.to] = d[cur] + next.weight;
preCity[next.to] = cur; // 이전마을 기록
pq.offer(new City(next.to, d[next.to]));
}
}
}
}
}
🌟 비슷한 유형의 문제들
❗ 풀어보면 좋은 문제들
참고
[java] 백준 11779 (최소비용 구하기2) Gold3
Author And Source
이 문제에 관하여([백준 11779] 최소비용 구하기2 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bobae1998/백준-11779-최소비용-구하기2-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)