티스토리 뷰
최단 경로 문제란?
- 최단 경로란 두 노드를 잇는 가장 짧은 경로를 찾는 문제
- 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적
최단 경로 문제 예시
- 단일 출발 및 단일 도착 최단 경로 문제
- u → v 에 도착하는 가장 짧은 경로를 찾는다.
- 단일 출발 최단 경로 문제
- 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
- 전체 쌍 최단 경로 문제
- 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제
이제 최단 경로 문제를 풀 때 사용하는 알고리즘에 대해 알아보자.
다익스트라
다익스트라는 위에 문제 예시에서 2번째에 해당한다.
- 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제
가장 보편화되어 있는 방식은 우선순위 큐를 활용하는 방식이다.
- 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
- 초기에는 첫 정점의 거리는 0, 나머지는 무한대(INF)로 저장한다.
- 우선순위 큐에 (첫 정점, 거리 0)[EDGE 클래스 선언] 만 먼저 넣음.
- 우선순위 큐에서 노드를 꺼냄
- 꺼낸 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 거리를 비교한다.
- 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
- 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
- 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.
다익스트라 예시 코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static List<Edge> map[];
static int[] distances; // 최단거리
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.valueOf(st.nextToken());
int dependencyCount = Integer.valueOf(st.nextToken());
int infectiousComputer = Integer.valueOf(st.nextToken());
map = new ArrayList[N + 1];
// 초기 거리는 무한대(INF)로 지정
distances = new int[N + 1];
Arrays.fill(distances, Integer.MAX_VALUE);
for (int i = 1; i <= N; i++) {
map[i] = new ArrayList<>();
}
for (int i = 0; i < dependencyCount; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.valueOf(st.nextToken());
int to = Integer.valueOf(st.nextToken());
int time = Integer.valueOf(st.nextToken());
map[to].add(new Edge(from, time));
}
// 다익스트라 시작
dijkstra(infectiousComputer);
int cnt = 0;
int time = 0;
for (int i = 1; i <= N; i++) {
if (distances[i] != Integer.MAX_VALUE) {
cnt++;
time = Math.max(time, distances[i]);
}
}
}
private static class Edge implements Comparable<Edge> {
private int from;
private int time;
Edge(int from, int time) {
this.from = from;
this.time = time;
}
// 최단 경로를 위해 compareTo를 오버라이드해준다.
@Override
public int compareTo(Edge o) {
return this.time - o.time;
}
}
private static void dijkstra(int infectiousComputer) {
PriorityQueue<Edge> queue = new PriorityQueue<>();
// 첫 정점의 거리는 0으로 설정
distances[infectiousComputer] = 0;
// 첫 정점과 0을 우선순위 큐에 넣어준다.
queue.add(new Edge(infectiousComputer, 0));
while (!queue.isEmpty()) {
Edge Edge = queue.poll();
int standardNode = Edge.from; // 기준 노드
int time = Edge.time; // 첫 정점에서 기준 노드와의 거리
if (distances[standardNode] < time) {
continue;
}
List<Edge> anotherEdges = map[standardNode]; // 기준 노드에 연결된 노드들의 리스트
for (Edge anotherEdge : anotherEdges) {
int nextFrom = anotherEdge.from; // 해당 노드
/**
* anotherEdge.time - 기준 노드 ~ 해당 노드 거리
* time : 첫 정점 노드 ~ 기준 노드
* 따라서, nextTime은 첫 정점 노드 ~ 기준 노드 ~ 해당 노드 거리
*/
int nextTime = anotherEdge.time + time;
// 첫 정점에서 해당 노드와의 거리(distances[nextFrom]과 nextTime을 비교 후 업데이트
if (distances[nextFrom] > nextTime) {
distances[nextFrom] = nextTime;
// 우선순위 큐에 넣어준다.
queue.add(new Edge(nextFrom, nextTime));
}
}
}
}
}
대표 문제
- [ ] 특정 거리의 도시 찾기
- [ ] 최단경로
- [ ] 최소비용 구하기
- [ ] 파티
- [ ] 알고스팟
- [ ] 특정한 최단 경로
- [ ] 숨바꼭질 3
- [ ] 녹색 옷 입은 애가 젤다지?
- [ ] 최소비용 구하기 2
'알고리즘' 카테고리의 다른 글
BOJ1753 최단경로 java - 다익스트라 (0) | 2022.01.29 |
---|---|
BOJ18352 특정 거리의 도시 찾기 java - 다익스트라 (0) | 2022.01.29 |
BOJ10282 해킹 java (0) | 2022.01.28 |
BOJ1325 효율적인 해킹 java (0) | 2022.01.28 |
BOJ1012 유기농 배추 java (0) | 2022.01.28 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 정규표현식
- kkoon9
- 디자인패턴
- programmers
- 이펙티브 자바
- 클린 코드
- 코테
- Java
- 객체지향
- 테라폼
- 백준
- Effective Java
- MSA
- Olympiad
- AWS
- BAEKJOON
- 프로그래머스
- Spring Boot
- 이팩티브 자바
- BOJ
- Spring
- 클린 아키텍처
- Algorithm
- Kotlin
- kotest
- 디자인 패턴
- C++
- 알고리즘
- node.js
- JPA
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함