• ํŒจ์ŠคํŠธ์บ ํผ์Šค ์ฑŒ๋ฆฐ์ง€ 4์ผ์ฐจ

    2021. 11. 4.

    by. JuneBee

    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
    ๋ฐ˜์‘ํ˜•

    ๋Œ“๊ธ€