사전 캠프 8일차

어제와 동일하게 DFS/ BFS 문제를 풀려고 했으나 문제를 풀던 도중 다익스트라 알고리즘에 관한 문제가 나왔고 BFS 로 푸니 메모리 초과가 나와 다익스트라 알고리즘에 대해 공부하고 정리해보기로 했다

 

1. 다익스트라 알고리즘이란? 

다익스트라 알고리즘이란 음의 가중치, 즉 음의 값이 없는 그래프의 한 노드에서 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.  

 

 

 

(1) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 (그리디 알고리즘)

(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 (다이나믹 프로그래밍)

 

2. 다익스트라 알고리즘의 특징

• 하나의 정점에서 출발하는 최단거리를 구한다.(출발지만 정해짐)
• 음수 가중치가 없어야한다.
• 인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2)
• 우선순위 큐를 이용한 경우 시간 복잡도를 O(mlogn)까지 낮출 수 있다.

나중에 배울 벨만-포드 알고리즘과 유사하나 벨만 포드는 시간 복잡도가 더 느린 대신 음수 가중치가 있어도 해결 가능하다!

 

3. 우선 순위 큐란?

우선 순위큐는 FIFI 형식의 큐가 아닌 우선 순위가 높은 데이터가 먼저나가는 형태의 자료 구조로 Heap 을 사용해서 구현한다.

 

3-1 Heap 이란?

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조로 부모노드와 서브트리간 대소 관계가 성립된 반정렬 상태이다.

 

힙의 장점

• 빠른 삽입 및 삭제 가능
• 우선 순위에 따라 작업 관리 가능

힙의 단점

• 임의 접근 어려움
• 정렬 유지에 오버헤드가 발생
• 배열로 구현 시 공간 할당에 어려움

Heap 예시 코드

 import java.util.PriorityQueue;
 PriorityQueue<Integer> minHeap = new PriorityQueue<>();
 //삽입
 minHeap.offer(5);
 
 //최솟값 확인
 System.out.println(minHeap.peek()); //5
 
  //최솟값 삭제
 System.out.println(minHeap.poll());

 

기본적으로 자바에서 제공하는 Heap은 최소 힙이며 offer, peek, poll 등 기본 큐와 유사한 메소드를 사용한다.

 

최대 힙을 사용하기 위해선 아래 코드를 사용하면 된다.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

 

---

4. 다익스트라 알고리즘 구현

1. 인접 리스트를 이용해서 그래프를 구현한다.

ArrayList<Node >[] graph;

class node{
	int no;
    int weight;
    public Node (int no, int weight){
    	this.no = no;
        this.weight = weight;
    }
}

 

2. 최단 거리 배열 초기화

int [] distance = new int [V+1];
for(int i=0; i<=v; i++){
	distance[i] = max;
}
distance[start] = 0;

 

3. 현재 값이 가장 작은 노드를 고른 후 최단 거리 배열 업데이트

if(distance[목표 노드] > distance[이전 노드] + 가중치){
	distance[목표 노드] = distance[이전 노드] + 가중치;
}

 

3번을 반복하여 완성!

---

백준 1753번 

https://www.acmicpc.net/problem/1753

 

개념을 배웠지만 실제로 적용시키기는 상당히 어려웠다. 다시 여러번 풀어서 확실히 익혀둬야할거 같다!

class Node{
	int end;
	int weight;
	public Node(int end, int weight) {
		this.end = end;
		this.weight = weight;
	}
}
public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int dist[]; //가중치를 담을 배열
	public static List<Node>[] list; // 간선에 대한 정보를 담을 리스트
	public static boolean visited[]; //방문 여부 체크 용 배열
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(bf.readLine());
		list = new ArrayList[V+1];
		dist = new int[V+1];
		visited = new boolean[V+1];
		for(int i=1;i<=V;i++) {
			list[i] = new ArrayList<>();
			dist[i] = Integer.MAX_VALUE;
		}
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(bf.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list[u].add(new Node(v,w));
		}
		dijkstra(V,E,K);
		print(V);
	}
	public static void dijkstra(int v, int e, int start) {
		PriorityQueue <Node> q = new PriorityQueue<>((x,y)->x.weight - y.weight);
		q.add(new Node(start,0));
		dist[start] = 0;
		while(!q.isEmpty()) {
			Node curNode = q.poll();
			int cur = curNode.end;
			if(visited[cur]) continue;
			visited[cur] = true;
			for(Node n : list[cur]) {
				if(dist[n.end] > dist[cur] + n.weight) {
					dist[n.end] = dist[cur] + n.weight;
					q.add(new Node(n.end,dist[n.end]));
				}
			}
		}
	}
	public static void print(int v) {
		for(int i=1;i<=v;i++) {
			if(dist[i] == Integer.MAX_VALUE) {
				System.out.println("INF");
			}
			else {
				System.out.println(dist[i]);
			}
		}
	}
}