-
728x90๋ฐ์ํ
๋ ์ง : 2021 ๋ 11 ์ 6 ์ผ
์์ฒญ ๊ฐ์ : ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ (1), ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ (2)์ค๋ ์์ฒญํ ๊ฐ์๋ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๋ด๊ฐ ๋ญ๋ค์๊ฑด๊ฐ์ถ๋ค ์ฃผ๋ฅด๋ฅต..ํฌ๋ฃจ์ค์นผ์ ์ดํด๊ฐ ์ข ๋ฌ๋๋ฐ ์ญ์ ์๋ ๋ถํฐ ํฌ๊ธฐํ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์ฐจ์์ด ๋ฌ๋๋ค..
์ผ๋จ ๊ฐ๋ ๋ง ์ดํดํ๊ณ ์ฝ๋๋ ๋์ค์ ์ดํดํ๊ธฐ๋ก ๊ฒฐ์ฌํ๋ค.
ํฌ๋ฃจ์ค์นผ vs ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ
1. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ : ๊ฐ์ ์ ๋ณด๋ฅผ ์ ๋ ฌ -> ๊ฐ์ฅ ๊ฐ์ค์น๊ฐ ๋ฎ์ ๊ฐ์ ๋ถํฐ ์ฌ์ดํด์ด ์๊ธฐ์ง ์๋๋ก ์ฐ๊ฒฐ
2. ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ : ์์ ์ ์ ์ ์ ํ -> ์ ์ ์ ์ธ์ ๊ฐ์ ์ค ๊ฐ์ค์น๊ฐ ์ต์์ธ ๊ฐ์ ์ ์ฐ๊ฒฐ
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ
https://www.cs.usfca.edu/~galles/visualization/Prim.html
Prim MST Visualzation
www.cs.usfca.edu
์ ์ฌ์ดํธ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์คํํด ๋ณด๋ฉด ๋์์ด ๋ง์ด ๋๋ ์ฐธ๊ณ ํด ๋ณด๋ฉด ์ข์ ๊ฒ ๊ฐ๋ค.
์ด๋ฏธ์ง ์ถ์ฒ : PNGWing ๊ตฌ๊ธ๋ก ๊ฒ์ํด์ ๋์ถฉ ์๋ฌด ๊ทธ๋ํ ์ฌ์ง์ ๊ฐ์ ธ์๋ดค๋ค.
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์, ์์์ ์ ์ ์ ์ ํํ์ฌ ๊ทธ์ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ค ๊ฐ์ค์น๊ฐ ์์ ์ ์ ์ ์ ํํ๊ธฐ๋ฅผ ๋ฐ๋ณตํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ฐ๋ผ์ ์ ๊ทธ๋ํ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํด๋ณด๋ฉด,
1. "A" ์ ํ : A-B(12), A-D(5) -> D ๋ ธ๋๋ฅผ ์ ํ
2. "A- D " : A-B(12), D-B(10), D-E(15) , D-F(6) -> F ๋ ธ๋๋ฅผ ์ ํ
3. "A - D - F " : A-B (12), D-B (10), D-E(15) , F-E(1) , F-G (11) -> E๋ ธ๋ ์ ํ
4. "A- D- F - E " : A-B (12), D-B (10), D-E(15) , F-G (11), E-B(7) , E-C(2), E-G(9) ->C๋ ธ๋ ์ ํ
5. "A- D- F - E - C" : A-B (12), D-B (10), D-E(15) , F-G (11), E-B(7) , E-G(9) , C-B(8) -> E์ ์ฐ๊ฒฐ๋ B๋ ธ๋ ์ ํ
G๋ง ์ฐ๊ฒฐํ๋ฉด ๋๋จ : ๊ฐ์ค์น๊ฐ ์์ E์ ์ฐ๊ฒฐ
A - D - F - E- C- G ๋ ธ๋๋ฅผ ์ ๋ถ ์ฐ๊ฒฐ : ์ต์ข ๊ฐ์ค์น : 5 + 6 + 1 + 2 + 7 + 9 = 30 ์ด ๋๋ค
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ
1. ์์์ ์ ์ ์ ํ -> ์ฐ๊ฒฐ๋ ๋ ธ๋ ์งํฉ์ ์ฝ์
2. ์ ํ ์ ์ ์ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ ๊ฐ์ ๋ฆฌ์คํธ์ ์ฝ์ -> ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ edge ์ถ์ถ
if ๊ฐ์ ์ ์ฐ๊ฒฐ๋ ์ธ์ ์ ์ ์ด ์ฐ๊ฒฐ๋ ๋ ธ๋ ์งํฉ์ ์๋ค๋ฉด ์ฌ์ดํด์ด ์๊ธฐ๋ฏ๋ก ์ ํ ์ํจ
else ๊ฐ์ ์ ์ฐ๊ฒฐํ๊ณ mst์ ๊ฐ์ ์ ๋ณด ์ฝ์
3. ์ถ์ถํ ๊ฐ์ ์ ๋ฆฌ์คํธ์์ pop
4. ๊ฐ์ ๋ฆฌ์คํธ๊ฐ ๋น๋๊น์ง 2-3 ์ ๋ฐ๋ณต๊ตฌํ์ ํ์ํ ๊ธฐ๋ฅ
๋ ธ๋ ํด๋์ค
public static class Node implements Comparable<Node>{ int weight, node1, node2; //setter method ๊ตฌํ @Override public int compareTo(Node node){ return this.weight - node.weight; } }
Priority Queue์ฌ์ฉ
๋ค์ต์คํธ๋ฆฌ์ฆ ์๊ณ ๋ฆฌ์ฆ๋์ฒ๋ผ, ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ์ฌ ์ต์ํ์ ๊ตฌํํ๋ค
import java.util.PriorityQueue;
ํ ์์ฑ ๋ฐ ์ถ๊ฐ
PriorityQueue<Node> p = new PriorityQueue<>(); p.offer(new Node (2 , "a", "b")); //๊ฐ์ค์น : 2, ์ฐ๊ฒฐ๋ ๋ ๋ ธ๋
HashMap ์ฌ์ฉ
Hashmap์ containsKey() ๋ฅผ ์ฌ์ฉํ์ฌ, ๊ฐ์ ์ ์ฐ๊ฒฐ๋ ์ธ์ ์ ์ ์ด ์ฐ๊ฒฐ๋ ๋ ธ๋ ์งํฉ์ ์ด๋ฏธ ์๋์ง๋ฅผ ํ๋จํ ์ ์๋ค.
HashMap<String, ArrayList<Node>> graph = new HashMap<>(); graph.put("a", new ArrayList<Node> ()); // a๋ฅผ ํด์ฌ๋งต์ ์ฝ์ // ํ์ a๊ฐ ์๋์ง ํ์ธ graph.getOrDefault("a", new ArrayList<Node>());
์๋ฐ ์ฝ๋ ๊ตฌํ
์๋ฐ ์ฝ๋๋ฅผ ๊ตฌํํ๊ธฐ ์ํด ํ์ํ ๋ฆฌ์คํธ๊ฐ ๊ฝค ๋ง์์ ๋ณต์กํ๋ค..
๋จผ์ , ๋๋ต์ ์ธ ์ฝ๋์ ํ๋ฆ์ ์๋์ ๊ฐ๋ค.
import java.util.HashMap; import java.util.PriorityQueue; public class PrimPath { //declare lists //Node class public ArrayList<Node> prime(String startNode, ArrayList<Node> ndoes){ //๋ฆฌ์คํธ ์ ์ธ //priority ํ ์ ์ธ //์ด๊ธฐํ //๊ฐ ๋ ธ๋๋ง๋ค ์ฐ๊ฒฐ๋ ๊ฐ์ ๋ฆฌ์คํธ ์ถ๊ฐ //์ฐ์ ์์ํ์ candiateEdgeList๋ฅผ ์ถ๊ฐ //์ฐ์ ์์ํ๊ฐ ๋น๋๊น์ง 2-3 ์๊ณ ๋ฆฌ์ฆ ๋ฐ๋ณต } }
๊ฐ์ ์ธ์ ๋ค๋ฅธ ์๋ฃ๋ค์ ์ฐพ์๋ณด๊ณ ์ข ๋ ์ฌ์ด ๋ฐฉ์์ด ์๋ค๋ฉด ๋ค์ ์๋ฐ ์ฝ๋ ๊ตฌํ์ ์ฌ๋ฆฌ๋๋ก ํ๊ฒ ๋ค.
๊ฐ์ ์ฝ๋๋ ๋ฆฌ์คํธ๊ฐ ๋๋ฌด ๋ง์ด ์ฐ์ฌ์ ๋ณต์กํ๊ฒ ๊ฐ๋ค.
ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ๋ฐ๋ก๊ฐ๊ธฐ๐ https://bit.ly/3FVdhDa
์๊ฐ๋ฃ 100% ํ๊ธ ์ฑ๋ฆฐ์ง | ํจ์คํธ์บ ํผ์ค
๋ฑ 5์ผ๊ฐ ์งํ๋๋ ํ๊ธ์ฑ๋ฆฐ์ง๋ก ์๊ฐ๋ฃ 100% ํ๊ธ๋ฐ์ผ์ธ์! ๋ ๋ฆ๊ธฐ์ ์ ์๊ธฐ๊ณ๋ฐ ๋ง์ฐจ ํ์น!
fastcampus.co.kr
๋ณธ ํฌ์คํ ์ ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ์ฐธ์ฌ๋ฅผ ์ํด ์์ฑ๋์์ต๋๋ค.
728x90๋ฐ์ํ'๐ STUDY > FASTCAMPUS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 8์ผ์ฐจ (0) 2021.11.08 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 7์ผ์ฐจ (0) 2021.11.07 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 5์ผ์ฐจ (0) 2021.11.05 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 4์ผ์ฐจ (0) 2021.11.04 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 3์ผ์ฐจ (0) 2021.11.03 ๋๊ธ