다익스트라(Dijkstra) 알고리즘은 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다익스트라 알고리즘은 음의 가중치를 갖는 간선이 없는 경우에 최적의 결과를 보장합니다. 다익스트라 알고리즘의 개념과 시간 복잡도에 대해 자세히 설명드리겠습니다.
- 개념:
- 출발 정점으로부터 각 정점까지의 최단 거리를 저장하는 배열을 초기화합니다. 출발 정점의 최단 거리는 0이고, 다른 정점들의 최단 거리는 무한대로 설정합니다.
- 우선순위 큐를 사용하여 최단 거리가 가장 작은 정점을 선택하고, 해당 정점과 연결된 정점들의 최단 거리를 업데이트합니다. 업데이트된 거리가 더 작은 경우에만 갱신합니다.
- 모든 정점을 방문할 때까지 위의 과정을 반복하여 최단 거리를 찾습니다.
- 시간 복잡도:
- 다익스트라 알고리즘의 시간 복잡도는 O((V + E) log V)입니다.
- 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다.
- 우선순위 큐를 사용하여 최단 거리가 가장 작은 정점을 선택하는 과정에서 각 정점은 최대 한 번씩만 처리되므로 O(V)입니다.
- 각 정점을 처리할 때마다 해당 정점과 연결된 간선들을 검사해야 하므로, 모든 간선에 대해 최대 한 번씩 검사하게 됩니다. 따라서 간선 검사의 시간 복잡도는 O(E)입니다.
- 우선순위 큐에 정점을 삽입하고 삭제하는 과정에서 각각 O(log V)의 시간이 소요됩니다.
- 따라서 총 시간 복잡도는 O((V + E) log V)입니다.
다익스트라 알고리즘은 가중치가 다른 그래프에서도 사용할 수 있으며, 정점 간의 최단 거리를 구하는 데에 효과적입니다. 하지만 음의 가중치를 가지는 간선이 있는 경우에는 다익스트라 알고리즘이 정확한 결과를 보장하지 않습니다.
다익스트라와 BFS의 차이점
BFS(Breadth-First Search)와 다익스트라(Dijkstra) 알고리즘은 둘 다 그래프에서 최단 경로를 찾는 알고리즘입니다. 그러나 두 알고리즘의 목적과 동작 방식에는 차이점이 있습니다.
- 목적:
- BFS: 출발 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 것이 아니라, 출발 정점에서 목표 정점까지의 최단 경로를 찾습니다. 따라서 BFS는 한 정점에서 다른 정점으로의 최단 경로를 찾는 단일 목적의 알고리즘입니다.
- 다익스트라: 출발 정점으로부터 그래프의 모든 정점까지의 최단 경로를 찾습니다. 다익스트라 알고리즘은 출발 정점에서 다른 모든 정점으로의 최단 경로를 찾는 다중 목적의 알고리즘입니다.
- 동작 방식:
- BFS: 너비 우선 탐색으로, 현재 정점과 인접한 정점들을 모두 탐색한 다음에 다음 레벨로 이동합니다. BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다.
- 다익스트라: 탐욕적인 방법을 사용하여 최단 거리를 갱신합니다. 각 단계에서 최단 거리가 가장 작은 정점을 선택하여 처리하고, 해당 정점과 연결된 정점들의 최단 거리를 업데이트합니다. 다익스트라 알고리즘은 우선순위 큐(Priority Queue) 자료구조를 사용하여 구현됩니다.
- 가중 그래프 처리:
- BFS: 가중 그래프에서 모든 간선의 가중치를 동일하게 취급합니다. 따라서 BFS는 가중치가 다른 간선을 고려하지 않고 최단 경로를 찾습니다.
- 다익스트라: 가중 그래프에서 각 간선의 가중치를 고려하여 최단 경로를 찾습니다. 다익스트라 알고리즘은 음의 가중치가 없는 경우에만 최적의 결과를 보장합니다.
요약하면, BFS는 단일 목적의 최단 경로를 찾는데 사용되며, 가중치가 동일한 그래프에서 작동합니다. 반면에 다익스트라는 다중 목적의 최단 경로를 찾는데 사용되며, 가중치가 다른 그래프에서도 작동합니다.
프로그래머스 - 배달
class Solution {
int[] dist;
int cnt = 0;
int[][] arr;
boolean[] visited;
public int solution(int N, int[][] road, int K) {
arr = new int[N + 1][N + 1];
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
arr[i][j] = 500001;
}
}
for (int i = 0; i < road.length; i++) {
if(arr[road[i][0]][road[i][1]] > road[i][2]) {
arr[road[i][0]][road[i][1]] = road[i][2];
arr[road[i][1]][road[i][0]] = road[i][2];
}
}
dist = new int[N + 1];
for (int i = 2; i < N + 1; i++) {
dist[i] = 500001;
}
visited = new boolean[N+1];
visited[1] = true;
dijkstra(N, K);
return cnt;
}
public void dijkstra(int n, int k) {
for (int i = 1; i < n; i++) {
int min = 500001;
int idx = 1;
for (int j = 2; j <= n; j++) {
if(!visited[j] && min > dist[j]) {
idx = j;
min = dist[j];
}
}
visited[idx] = true;
for (int j = 2; j <= n ; j++) {
if(dist[j] > dist[idx] + arr[idx][j]) {
dist[j] = dist[idx] + arr[idx][j];
}
}
}
for (int i = 1; i <= n ; i++) {
if(dist[i] <= k) {
cnt++;
}
}
}
}
백준 - 5792
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
static int[] dist;
static boolean[] visited;
static List<Node>[] list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
list = new ArrayList[n+1];
for(int i = 1; i <= n; i++) {
list[i] = new ArrayList<>();
}
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
list[a].add(new Node(b, c));
list[b].add(new Node(a, c));
}
dist = new int[n+1];
visited = new boolean[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dijkstra();
System.out.println(dist[n]);
}
public static void dijkstra() {
PriorityQueue<Node> q = new PriorityQueue<>();
dist[1] = 0; //시작 지점은 1
q.offer(new Node(1, 0));
while(!q.isEmpty()) {
Node current = q.poll();
if(!visited[current.location]) visited[current.location] = true;
else continue;
for(int i = 0; i < list[current.location].size(); i++) {
Node next = list[current.location].get(i);
if(dist[next.location] > dist[current.location] + next.cost) {
dist[next.location] = dist[current.location] + next.cost;
q.offer(new Node(next.location, dist[next.location]));
}
}
}
}
public static class Node implements Comparable<Node> {
int location;
int cost;
public Node(int location, int cost) {
this.location = location;
this.cost = cost;
}
@Override
public int compareTo(Node n) {
return this.cost - n.cost;
}
}
}
백준 4485
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
static int[][] dist;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, -1, 0, 1};
static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int cnt = 0;
while(n != 0) {
cnt ++;
map = new int[n][n];
dist = new int[n][n];
visited = new boolean[n][n];
for(int i=0; i<n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dijkstra();
System.out.println("Problem " + cnt + ": " + dist[n-1][n-1]);
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
}
}
public static void dijkstra() {
dist[0][0] = map[0][0];
PriorityQueue<Node> q = new PriorityQueue();
q.offer(new Node(0,0, dist[0][0]));
while(!q.isEmpty()) {
Node current = q.poll();
if(!visited[current.row][current.col]) visited[current.row][current.col] = true;
else continue;
for(int i = 0; i <4; i++) {
int ny = current.row + dy[i];
int nx = current.col + dx[i];
if(0 <= ny && ny < n && 0 <= nx && nx < n) {
if(dist[ny][nx] > map[ny][nx] + dist[current.row][current.col]) {
dist[ny][nx] = map[ny][nx] + dist[current.row][current.col];
q.offer(new Node(ny, nx, dist[ny][nx]));
}
}
}
}
}
public static class Node implements Comparable<Node> {
int row;
int col;
int cost;
public Node(int row, int col, int cost) {
this.row = row;
this.col = col;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
}'코딩 테스트 수련의방 > 알고리즘' 카테고리의 다른 글
| LIS 알고리즘 (0) | 2023.08.09 |
|---|---|
| 크루스칼 알고리즘 (0) | 2023.06.18 |
| 투 포인터 알고리즘 (0) | 2023.06.17 |
| DP 알고리즘 (0) | 2023.06.12 |
| DFS 알고리즘 (0) | 2023.06.09 |
댓글