[백준 1504번 / Java] 특정한 최단 경로 - 다익스트라(Dijkstra)코딩테스트/백준2023. 8. 14. 06:21
Table of Contents
728x90
728x90
문제 링크
Gold 4
https://www.acmicpc.net/problem/1504
풀이
방향성이 없는 그래프가 주어졌으며, 이는 양방향으로 구현해야 함
또한 주어진 두 가지의 경로 v1, v2를 모두 통과한 후 최종 지점으로 도착할 수 있는 경로를 구해야한다는 점이다.
1번에서 출발해서 v1, v2를 거쳐 최종 목적지로 도착하는 방법은 두 가지가 있으며 이를 쪼개면 다음과 같이 표현할 수 있다.
1 → v1 → v2 → goal
// 1 → v1
// v1 → v2
// v2 → goal
1 → v2 → v1 → goal
// 1 → v2
// v2 → v1
// v1 → goal
위에서 종합한 조건들을 바탕으로 기본 다익스트라 알고리즘을 구현한 코드 위에 아래 세 가지만 고려하여 작성하면 된다.
1. 양방향으로 구현하기 때문에 반대의 경우도 노드 리스트에 추가
for(int i = 0; i < E; i ++) {
st = new StringTokenizer(br.readLine(), " ");
int before = Integer.parseInt(st.nextToken());
int after = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
//단방향
nodeList.get(before).add(new Node(after, weight));
//양방향
nodeList.get(after).add(new Node(before, weight));
}
2. 파라미터로 각 조건을 분할해서 수행하면 코드의 재사용성을 극대화할 수 있음
int distV1 = 0;
distV1 += dist(1, v1);
distV1 += dist(v1, v2);
distV1 += dist(v2, N);
int distV2 = 0;
distV2 += dist(1, v2);
distV2 += dist(v2, v1);
distV2 += dist(v1, N);
private static int dist(int start, int end) {
//코드
}
3. Integer.MAX_VALUE로 초기화한 기존 dist배열을 문제 조건에 맞게. 간선 개수(200,000) * 거리(1000)의 최대 값인 2억개로 셋팅해준다.
private static int INF = 200000000;
Arrays.fill(dist, INF);
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int N;
private static int E;
private static int v1;
private static int v2;
private static int[] dist;
private static boolean[] visited;
private static List<List<Node>> nodeList = new ArrayList<>();
private static int INF = 200000000;
static class Node implements Comparable<Node> {
int node;
int cost;
public Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return cost - o.cost;
}
}
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());
E = Integer.parseInt(st.nextToken());
for(int i = 0; i <= N; i ++) {
nodeList.add(new ArrayList<>());
}
for(int i = 0; i < E; i ++) {
st = new StringTokenizer(br.readLine(), " ");
int before = Integer.parseInt(st.nextToken());
int after = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
nodeList.get(before).add(new Node(after, weight));
nodeList.get(after).add(new Node(before, weight));
}
st = new StringTokenizer(br.readLine(), " ");
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
dist = new int[N + 1];
visited = new boolean[N + 1];
int distV1 = 0;
distV1 += dist(1, v1);
distV1 += dist(v1, v2);
distV1 += dist(v2, N);
int distV2 = 0;
distV2 += dist(1, v2);
distV2 += dist(v2, v1);
distV2 += dist(v1, N);
System.out.println(distV1 >= INF && distV2 >= INF ? -1 : Math.min(distV1, distV2));
}
private static int dist(int start, int end) {
Arrays.fill(dist, INF);
Arrays.fill(visited, false);
dist[start] = 0;
PriorityQueue<Node> nodeQueue = new PriorityQueue<>();
nodeQueue.offer(new Node(start, 0));
while (!nodeQueue.isEmpty()) {
Node curNode = nodeQueue.poll();
int cur = curNode.node;
if(!visited[cur]) {
visited[cur] = true;
for(Node node : nodeList.get(cur)) {
if(!visited[node.node] && dist[node.node] > dist[cur] + node.cost) {
dist[node.node] = dist[cur] + node.cost;
nodeQueue.offer(new Node(node.node, dist[node.node]));
}
}
}
}
return dist[end];
}
}
728x90
300x250
@mag1c :: 꾸준히 재밌게
2023.04 ~ 백엔드 개발자의 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!