-
728x90๋ฐ์ํ
๋ ์ง : 2021 ๋ 11 ์ 4 ์ผ
์์ฒญ ๊ฐ์ : ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ์ดํด (1) , ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ์ดํด (2) , ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ ์ดํด (3) ,์ต๋จ ๊ฒฝ๋ก - ๋ค์ต์คํธ๋ผ
๊ฐ์ค์น ๊ทธ๋ํ์์ ๊ฐ์ ์ ๊ฐ์ค์น ํฉ์ด ์ต์๊ฐ ๋๋๋ก ํ๋ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๊ฒ
์ ํ
1. ๋จ์ผ ์ถ๋ฐ (๋ค์ต์คํธ๋ผ)
ํน์ ๋ ธ๋ -> ๋ชจ๋ ๊ทธ๋ํ ๋์๋ค๋๋ฉด์ ๊ฐ์ฅ ์งง์ ๊ฒฝ๋ก ์ฐพ๊ธฐ
2. ๋จ์ผ ๋์ฐฉ
๋ชจ๋ ๋ ธ๋์์ ์ถ๋ฐ -> ํน์ ๋ ธ๋๋ก ๋์ฐฉํ๋ ๊ฐ์ฅ ์งง์ ๊ฒฝ๋ก
3. ๋จ์ผ์
u~ V๊น์ง์ ์ต์ ๊ฒฝ๋ก (1 ๊ฐ)
4. ์ ์ฒด์
๋ชจ๋ ์์ ๋ํ ์ต๋จ ๊ฒฝ๋ก
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ค
์ฐ์ ์์ ํ๋ฅผ ํ์ฉํ์ฌ ํ์ดํ๋ ๋ฐฉ์์ BFS ๋ฐฉ์๊ณผ ๋งค์ฐ ์ ์ฌํ๋ฐ, ์ด๋ ์์๋ ์ฐ๊ฒฐ๋ ๋ ธ๋๋ฅผ ์ฒดํฌํ์ฌ ํ์ํ๊ธฐ ๋๋ฌธ์ด๋ค.https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
Dijkstra Visualzation
www.cs.usfca.edu
์ ์ฌ์ดํธ๋ฅผ ํตํด ๋ค์ต์คํธ๋ผ ๊ตฌํ ๋ฐฉ์์ ํ๋ฒ ๋ณด๋ ๊ฒ์ ์ถ์ฒํ๋ค.
๋ค์ต์คํธ๋ผ๋, ๋ ธ๋์ ๋ณธ์ธ ๋ ธ๋๊ฐ ์ฐ๊ฒฐ๋์ง ์์๋ค๋ฉด ∞ ๋ฅผ, ๊ทธ๋ ์ง ์๋ค๋ฉด ๋ณธ์ธ๊ณผ์ ๊ฑฐ๋ฆฌ (๋ณธ์ธ์ด๋ฉด 0) ์ ๊ทธ๋ํ์ ๋ฃ์ด์ inf ๊ฐ ์๋ ๋ ธ๋๋ค์ ํ์ํ๋ฉฐ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ํ์ํ๋ ๋ฐฉ์์ด๋ค.
์ ์์๋ฅผ ์ดํด๋ณด์.
๋ ธ๋ "0" ์ ์ด๋ ํ ๋ ธ๋์๋ ์ฐ๊ฒฐ๋์ด ์์ง ์๋ค (1๊ณผ 2๋ 0์ผ๋ก ๊ฐ๋ ๋ฐฉํฅ์ผ ๋ฟ, 0์์ ๊ฐ ์ ์๋ค).
์ด ๊ด๊ณ๋ฅผ ๋ค์ต์คํธ๋ผ๋ก ํํํด ๋ณด์๋ฉด,
๋ ธ๋ 0 ๋ ธ๋ 1 ๋ ธ๋ 2 ๋ ธ๋ 3 ๋ ธ๋ 4 ๋ ธ๋ 5 ๋ ธ๋ 6 ๋ ธ๋ 7 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ๋ ธ๋ "1" ์ ์ดํด๋ณด๋ฉด, ๋ ธ๋ 5์ 6์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์์ ํ์ธํด ๋ณผ ์ ์๋ค.
์ด๋ ์๋์ ๊ฐ์ด ํํํ๋ค.
๋ ธ๋ 0 ๋ ธ๋ 1 ๋ ธ๋ 2 ๋ ธ๋ 3 ๋ ธ๋ 4 ๋ ธ๋ 5 ๋ ธ๋ 6 ๋ ธ๋ 7 5 0 ∞ ∞ ∞ 5 3 ∞ ๋ฐ๋ผ์, ๋ค์ต์คํธ๋ผ ๋ฐฉ์์ผ๋ก ์ ๊ฒฝ๋ก๋ฅผ ๋ฐฐ์ด ํํ๋ก ๋ํ๋ด ๋ณด๋ฉด
๋น ๊ณต๊ฐ์ ∞ ์ด๋ค. ๋, ๋ฆฌ์คํธ ํํ๋ก ๋ํ๋ด๋ฉด
์์ ๊ฐ์ด ํํํด ๋ณผ ์ ์๋ค.
๋ ธ๋ 0, 1, 2๋ฅผ ๋ค์ต์คํธ๋ผ ๋ฐฉ์์ผ๋ก ๊ตฌํํ๋ฉด
๋ค์ต์คํธ๋ผ 0~2 ๊ตฌํ ์ ๋๋ฉ์ด์ ์๋ฐ ์ฝ๋
๊ตฌํ ๊ณผ์
์ธ๋ถ ํด๋์ค ์์ฑ
1. ๋ ธ๋ ํด๋์ค ์์ฑ
2. Comparator() ์ค๋ฒ๋ผ์ด๋
3. toString() ์ค๋ฒ๋ผ์ด๋
PriorityQueue ์ฌ์ฉ
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ1. ๋ ธ๋ ํด๋์ค๋ฅผ ์์ฑํ๋ค
BFS์์ ํ๋ ๋ฐฉ์๊ณผ ๋์ผํ ๋ฐฉ์์ผ๋ก, constructor๋ฅผ ์์ฑํ๋ค.
public class Node implements Comparable <Node> { int distance ; //๊ฐ์ค์น (w) ํน์ ๊ฑฐ๋ฆฌ String vertex; public Edge(int distance, String vertex){ this.distnace; this.vertex; } //Overrides goes here }
2. Comparator( )
@override public int compareTo(Node node){ return this.distance - node.distance; }
PriorityQueue๋ฅผ ์ฌ์ฉํ๊ธฐ ์ํด์, compareTo๋ฅผ override ํด์ฃผ์ด ๊ฑฐ๋ฆฌ์์ผ๋ก ์ ๋ ฌ๋๊ฒ ํด์ค๋ค.
3. toString( )
@Override public String toString(){ return "node : " + this.node + ", distance : " + this.distance; }
4. PriorityQueue
import java.util.PriorityQueue;
์ import ๋ฌธ์ ํตํด importํด์ค๋ค.
PriorityQueue์ ์ฌ์ฉ ๋ฐฉ๋ฒ์ ์ผ๋ฐ ํ์ ๋น์ทํ๋ค. ๋ค๋ฅธ ์ ์ด ์๋ค๋ฉด, ์ต์ํ์ฒ๋ผ ๊ฐ์ฅ priority (ํ์ฌ๋ compareTo์์ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ์์ด priority๊ฐ ๋๋ค) ์ด ํ์ ๋งจ ์๋ก ์์ด๋ ๊ตฌ์กฐ์ด๋ค.
PriorityQueue <Node> q = new PriorityQueue<Node> (); //q ์์ฑ q.offer(new Node(2, "A")); //add q.poll();//poll out q.peek(); //๋งจ ์์๊ฐ์ ๋ณธ๋ค
์์ ์ฝ๋์ฒ๋ผ ์ฐ์ ์์ํ๋ฅผ ์์ฑ, ์ถ๊ฐ ๋ฐ ์ญ์ ํ ์ ์๋ค.
๋๋ q.add(new ~~) ๋ณด๋ค๋ q.offer()์ ์ ํธํ๋ค.
์ทจํฅ์กด์ค5. HashMap
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๊ธฐ ์์, ํ์ฌ ๊ตฌํ๋ ค๋ ๊ทธ๋ํ๋ฅผ HashMap์ ํตํ์ฌ ์ ๋ ฅํด์ผ ํ๋ค.
HashMap<String , ArrayList<Node>> graph = new HashMap<>(); //ํด์ฌ๋งต ์์ฑ //"A"๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ ธ๋๋ค๊ณผ ๊ฑฐ๋ฆฌ๋ฅผ ๋ฆฌ์คํธ ํํ๋ก ์ ๋ ฅ graph.put("A", new ArrayList<Node> (Arrays.asList(new Node (8, "B"), new Node(1 , "C"), new Node (1 , "D"));
์ ํด์ฌ๋งต ๊ตฌ์กฐ์์, ๋ชจ๋ ๋ ธ๋์ ์ฐ๊ฒฐ ๊ด๊ณ๋ฅผ ๋ณด๊ณ ์ถ๋ค๋ฉด,
ํด์ฌ.keySet() ๋ฅผ ์ด์ฉํ์ฌ iterate ํ๋ฉฐ, get(key) ํ๋ฉด ๊ด๊ณ๋ฅผ ํ๋ฆฐํธํ์ฌ ๋ณผ ์ ์๋ค.
for(String key : graph.keySet()){ System.out.print("Node " + key + " : "); System.out.println(graph.get(key)); }
6. ์ ์ฒด ๊ตฌ์กฐ
import java.util.PriorityQueue; import java.util.HashMap; import java.util.Arrays; import java.util.ArrayList; public class DijkstraPath { //๋ ธ๋ ํด๋์ค public static class Node{ int distance, String node ; //constructor ์์ฑํ๊ธฐ //toString ์์ฑํ๊ธฐ //compareTo ์ค๋ฒ๋ผ์ด๋ํ๊ธฐ } public HashMap<String, Integer> dijkstraFunc(HashMap<String, ArrayList<Node>> graph, String start) { //input ๋ฐ๊ธฐ /*๊ฑฐ๋ฆฌ ํด์ฌ๋งต์ INF ๋ก ์ด๊ธฐํ ์ํจ๋ค*/ HashMap<String, Integer> distances = new HashMap<String, Integer>(); for (String key : graph.keySet()) { distances.put(key, Integer.MAX_VALUE); } /*์์ ๋ ธ๋์ ๊ฑฐ๋ฆฌ 0 ์ ์ค๋ค*/ distances.put(start, 0); /*ํ ์์ฑ ๋ฐ ์์ ๋ ธ๋ ์ฝ์ */ PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>(); priorityQueue.offer(new Node(distances.get(start), start)); /*์๊ณ ๋ฆฌ์ฆ ์์ฑ : BFS์ ๋น์ทํ ๊ตฌ์กฐ*/ while (!priorityQueue.isEmpty()) { /*ํ์ ์๋ ์ต์๊ฐ poll*/ edgeNode = priorityQueue.poll(); /* ์ต์๊ฐ ์๋๋ผ๋ฉด continue ํด์ฃผ์..*/ if (distances.get(currentNode) < edgeNode.distance) { continue; } /* ๋ ธ๋ ๋ฆฌ์คํธ์ ํ์ฌ ๋ ธ๋์ ์ฐ๊ฒฐ๋ ๋ ธ๋๋ค์ ์ ๋ถ ๋ํด์ค๋ค */ nodeList = graph.get(edgeNode.node); /* ์ธ์ ๋ ธ๋ */ for (int index = 0; index < nodeList.size(); index++) { adjacentNode = nodeList.get(index); //์ธ์ ๋ ธ๋ get adjacent = adjacentNode.node; //์ธ์ ๋ ธ๋์ ๋ ธ๋get weight = adjacentNode.distance; //์ธ์ ๋ ธ๋์ ์ ์ฅ๋ distance get distance = edgeNode.distance + weight;// ์ ๊ฑฐ๋ฆฌ = ํ์ฌ ๊ฑฐ๋ฆฌ์ ์ธ์ ๋ ธ๋์ ๊ฑฐ๋ฆฌ if (distance < distances.get(adjacent)) { //์ ๊ฑฐ๋ฆฌ๊ฐ ํ์ฌ ๊ฑฐ๋ฆฌ๋ณด๋ค ์์ผ๋ฉด (์ต์)๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์ค์ด๋ฏ๋ก ํ์ ๋ค์ด๊ฐ ์๊ฒฉ์ด ์๋ค distances.put(adjacent, distance); priorityQueue.offer(new Node(distance, adjacent)); } //์ ๊ฑฐ๋ฆฌ๊ฐ ๋ ํฌ๋ฉด ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์ค์ด๋ฏ๋ก ๋ฃ์ง ์๋๋ค.. } } return distances; } }
ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ๋ฐ๋ก๊ฐ๊ธฐ๐ https://bit.ly/3FVdhDa
์๊ฐ๋ฃ 100% ํ๊ธ ์ฑ๋ฆฐ์ง | ํจ์คํธ์บ ํผ์ค
๋ฑ 5์ผ๊ฐ ์งํ๋๋ ํ๊ธ์ฑ๋ฆฐ์ง๋ก ์๊ฐ๋ฃ 100% ํ๊ธ๋ฐ์ผ์ธ์! ๋ ๋ฆ๊ธฐ์ ์ ์๊ธฐ๊ณ๋ฐ ๋ง์ฐจ ํ์น!
fastcampus.co.kr
๋ณธ ํฌ์คํ ์ ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ์ฐธ์ฌ๋ฅผ ์ํด ์์ฑ๋์์ต๋๋ค.
728x90๋ฐ์ํ'๐ STUDY > FASTCAMPUS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 6์ผ์ฐจ (0) 2021.11.06 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 5์ผ์ฐจ (0) 2021.11.05 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 3์ผ์ฐจ (0) 2021.11.03 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 2์ผ์ฐจ (0) 2021.11.02 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 1์ผ์ฐจ (0) 2021.11.01 ๋๊ธ