โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

6. Union Find(ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) : MST - 1

Union Find (ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) MST - 1 ์ •๋ง ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. MST ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋˜ ๋„์ค‘ ์ƒ๊ฐ๋‚˜์„œ ํฌ์ŠคํŒ… ํ•˜๊ฒŒ ๋๋‹ค. ๋งค์ฃผ ์ฃผ๋ง๋งˆ๋‹ค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ์ •๋ฆฌ๋ฅผ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ ๊ณ„์† ์‹คํŒจํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค... ใ…Žใ…Ž;; ์˜ค๋Š˜ ๋‹ค๋ค„๋ณผ ์ฃผ์ œ๋Š” MST, ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๊ธฐ๋ณธ ๋ฒ ์ด์Šค์ธ Union Find์ด๋‹ค. ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์—๋Š” ๋Œ€ํ‘œ์ ์œผ๋กœ ํฌ๋ฃจ์Šค์นผ(Kruskal)๊ณผ ํ”„๋ฆผ(Prim) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•œ๋‹ค. Union FInd๋Š” ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ต์‹ฌ์ด๋ผ๊ณ  ๋งํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿผ Union Find๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋ณด์ž. Union Find๋Š” ๋ง ๊ทธ๋Œ€๋กœ Union, ์ง‘ํ•ฉ์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ทธ๋ž˜ํ”„ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ์ด๋“ค ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ์•Œ์•„๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋ฐ”๋กœ ์˜ˆ์‹œ..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

5. Floyd Warshall(ํ”Œ๋ฃจ์ด๋“œ ์™€์ƒฌ) : ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 3

Floyd Warshall (ํ”Œ๋ฃจ์ด๋“œ ์™€์ƒฌ) ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 3 ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. ์ฃผ๋ง๋งˆ๋‹ค ํ•œ ๊ฐœ์”ฉ์€ ์“ธ๋ผํ–ˆ๋Š”๋ฐ ์ฃผ๋ง์— ์ข€ ๋ฐ”๋น ์„œ ๋ชป์ผ๋‹ค... ์–ด์ œ ๋ฐฑ์ค€์—์„œ ํ”Œ๋ฃจ์ด๋“œ ์™€์ƒฌ ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ๊ฐ‘์ž๊ธฐ ๋ธ”๋กœ๊ทธ ํฌ์ŠคํŒ…์ด ์ƒ๊ฐ๋‚˜์„œ ์“ฐ๊ฒŒ ๋๋‹ค! ๋‹ค์ต์ŠคํŠธ๋ผ, ๋ฒจ๋งŒ ํฌ๋“œ์— ์ด์€ ํ”Œ๋ฃจ์ด๋“œ ์™€์ƒฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋งˆ์ง€๋ง‰ ๋‚ด์šฉ์ด๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ, ๋ฒจ๋งŒ ํฌ๋“œ๋Š” ํŠน์ • ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋…ธ๋“œ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•ด์ค€๋‹ค. ์กฐ๊ธˆ ์ƒ๊ฐ์„ ๋ฐ”๊ฟ”์„œ ๋ชจ๋“  ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋…ธ๋“œ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•˜๋ ค๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ• ๊นŒ? ์šฐ์„  ๊ธฐ์กด์— ๋ฐฐ์› ๋˜ ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๋ฒจ๋งŒ ํฌ๋“œ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํƒ์ƒ‰ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ์—์„œ ์ž…๋ ฅ ๊ฐ’์œผ๋กœ ๋„ฃ์–ด์ฃผ๋Š” src, ์ฆ‰ ์ถœ๋ฐœ ๋…ธ๋“œ๋ฅผ ๋ชจ๋“  ๋…ธ๋“œ๋กœ ์„ค์ •ํ•˜๋ฉด ๋œ๋‹ค. ๊ทธ๋งŒํผ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ์•„์•ผํ•˜๊ธฐ์— ์‹œ๊ฐ„๋ณต์žก๋„๋Š” N๋งŒ..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

4. Bellman-Ford(๋ฒจ๋งŒ ํฌ๋“œ) : ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 2

Bellman Ford (๋ฒจ๋งŒ ํฌ๋“œ) ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 2 ์˜ค๋Š˜์€ ์ง€๋‚œ๋ฒˆ ๋‹ค์ต์ŠคํŠธ๋ผ์— ์ด์–ด ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ •๋ฆฌํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์ง€๋‚œ๋ฒˆ ๋‹ค์ต์ŠคํŠธ๋ผ ํฌ์ŠคํŒ…์—์„œ ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” ์Œ์˜ ์‚ฌ์ดํด์ด ์žˆ๋Š” ๊ทธ๋ž˜ํ”„์—์„œ๋Š” ์‚ฌ์šฉ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค๊ณ  ํ•˜์˜€๋‹ค. ๊ทธ ์ด์œ ๋Š” ๋ฌด์—‡์ผ๊นŒ? ์šฐ์„ , ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„์˜ ์‹œ์ž‘ ์ •์ ์ด A๋ผ๊ณ  ํ–ˆ์„ ๋•Œ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•ด๋ณด์ž. [์˜ˆ์ƒ ๊ฒฐ๊ณผ] A : 0 B : -4 C : 3 D : -7 E : 1 F : -3 [์‹ค์ œ ๊ฒฐ๊ณผ] ์‹œ์ž‘ ์ •์ ์—์„œ ์ด์ƒํ•œ ๊ฐ’์ด ์ถœ๋ ฅ๋˜๋Š” ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋‹ค๋ฅธ ์˜ˆ์‹œ๋ฅผ ๋ณด์ž. [์˜ˆ์ƒ ๊ฒฐ๊ณผ] A : 0 B : 2 ( ์žฌ๋ฐฉ๋ฌธ์„ ํ•˜์ง€ ์•Š๋Š”๋‹ค๊ณ  ๊ฐ€์ •) C : 5 D : 1 E : 3 [์‹ค์ œ ๊ฒฐ๊ณผ] ์—ญ์‹œ, E ์ •์ ์—์„œ ์ด์ƒํ•œ ๊ฐ’์ด ์ถœ๋ ฅ๋˜๋Š” ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ์ด์œ ๊ฐ€ ๋ญ˜๊นŒ?..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

3. Dijsktra(๋‹ค์ต์ŠคํŠธ๋ผ) : ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 1

Dijsktra (๋‹ค์ต์ŠคํŠธ๋ผ) ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 1 ์ •๋ง ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. ์›๋ž˜ ๋ชฉํ‘œ๋Œ€๋กœ ์ง„ํ–‰ํ–ˆ์œผ๋ฉด ๊ฐœ๊ฐ•์„ ํ•˜๊ธฐ ์ „์— DP๊นŒ์ง€ ํฌ์ŠคํŒ…์„ ํ–ˆ์–ด์•ผํ•˜๋Š”๋ฐ ์š”์ƒˆ ์กฐ๊ธˆ ๋ฐ”๋นด๋‹ค...(์‚ฌ์‹ค ์˜์š•์ด ์—†๋˜๊ฑธ ์ˆ˜๋„...) ์•„๋ฌดํŠผ ์ด๋ฒˆ 3-1 ๊ณผ๋ชฉ์— ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‘์šฉ์ด๋ผ๋Š” ๊ณผ๋ชฉ์„ ์ˆ˜๊ฐ•ํ•˜๋Š”๋ฐ ์ž‘๋…„์—๋Š” ๋”ฅ๋Ÿฌ๋‹๊ณผ ๊ด€๋ จํ•˜์—ฌ ์ˆ˜์—…ํ–ˆ๋‹ค๊ณ ํ•ด์„œ ์‹ ์ฒญํ–ˆ๋Š”๋ฐ ์ด๋ฒˆ์— ๊ต์ˆ˜๋‹˜์ด ๋ฐ”๋€Œ๋ฉด์„œ ์ •๋ง ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด ํ•™์Šตํ•˜๋Š” ์ˆ˜์—…์ด ๋˜์–ด๋ฒ„๋ ธ๋‹ค. ์‚ด์ง ์•„์‰ฌ์› ์ง€๋งŒ ๊ฐ•์˜๊ณ„ํš์„œ๋ฅผ ๋ณด๋‹ˆ 2-2 ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…๊ณผ ๊ฑฐ์˜ ๋น„์Šทํ•ด์„œ? ํ•™๊ธฐ ์ดˆ์— ๋ฏธ๋ฆฌ๋ฏธ๋ฆฌ ์ •๋ฆฌํ•ด๋‘๋ ค๊ณ  ํ•œ๋‹ค. ์„œ๋ก ์ด ๊ธธ์—ˆ๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•ด๋ณด์ž. graph ๋ณ€์ˆ˜์— ์—ฐ๊ฒฐ๋œ ์ •์ ๊ณผ ๊ฐ€์ค‘์น˜๊ฐ€ ์ €์žฅ๋˜์–ด ์žˆ๋‹ค๊ณ  ๋ณธ๋‹ค. graph[1] = [2..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

2. DFS(Depth-Find-Search) : ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰

DFS(Depth-Find-Search) ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์ง€๋‚œ ์‹œ๊ฐ„ BFS์— ์ด์–ด ์˜ค๋Š˜์€ DFS์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๋ ค๊ณ  ํ•œ๋‹ค. DFS๋Š” Depth-Find-Search๋กœ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋‹ค. BFS์™€ ๋‹ค๋ฅด๊ฒŒ DFS๋Š” ๊นŠ์ด๋ฅผ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•œ๋‹ค. ์ฆ‰ ์ตœ๋Œ€ ๊นŠ์ด๊นŒ์ง€ ์žฌ๊ท€์ ์œผ๋กœ ์ด๋™ํ•œ ํ›„ ์ตœ๋Œ€ ๊นŠ์ด์— ๋„๋‹ฌํ•œ ๊ฒฝ์šฐ ์˜†์œผ๋กœ ์ด๋™ํ•œ๋‹ค. ๋˜ํ•œ BFS์—์„œ๋Š” Queue๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค๋ฉด DFS์—์„œ๋Š” Stack์„ ์‚ฌ์šฉํ•œ๋‹ค. ์ด Stack์— ์ €์žฅ๋œ ๊ฐ’์ด ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” DFS์˜ ํƒ์ƒ‰ ์ˆœ์„œ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘ ๋ฐฉ์‹ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1. ํŠน์ • ์ •์ ์ด ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ธ ๊ฒฝ์šฐ ์ด๋ฅผ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ ํ•ด์ค€๋‹ค. 2. ํ•ด๋‹น ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋œ ๋‹ค๋ฅธ ์ •์ ์— ๋Œ€ํ•ด ์œ„ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ DFS๋ฅผ ์ ์šฉํ•ด๋ณด์ž. โ‘  ์‹œ์ž‘ ์ •์ ์„ 8..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

1. BFS(Breath-Find-Search) : ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰

BFS(Breath-Find-Search) ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ๊ทธ๋ž˜ํ”„์˜ ํƒ์ƒ‰ ๋ฐฉ๋ฒ• ์ค‘ ํ•˜๋‚˜์˜ BFS์— ๋Œ€ํ•ด์„œ ์‚ดํŽด๋ณด๋ ค๊ณ  ํ•œ๋‹ค. BFS๋Š” ๋ง ๊ทธ๋Œ€๋กœ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰, ์ฆ‰ ํŠน์ • Vertice์—์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด Vertice๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•œ๋‹ค๋Š” ๋œป์ด๋‹ค. ์šฐ์„  BFS๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” Queue๊ฐ€ ํ•„์š”ํ•˜๋‹ค. Stack, Queue, Heap์— ๋Œ€ํ•ด์„œ๋Š” ๋‚˜์ค‘์— ์ž์„ธํžˆ ์„ค๋ช…ํ•˜๊ธฐ๋กœ ํ•˜๊ณ  Queue์— ๋Œ€ํ•ด ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜์ž๋ฉด FIFO(First in First out - ์„ ์ž…์„ ์ถœ)์œผ๋กœ ๋™์ž‘ํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์œ„์—์„œ๋„ ๋งํ–ˆ๋“ฏ์ด BFS์˜ ๊ฐ€์žฅ ํฐ ๊ฐœ๋…์€ ๊ฐ€๊นŒ์šด ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋˜, ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ธ ๊ฒฝ์šฐ ๋ฐฉ๋ฌธ ๋ฆฌ์ŠคํŠธ์— ์ •์ ์„ ์ €์žฅํ•˜๋ฉด ๋œ๋‹ค. ์ด ๋ฐฉ๋ฌธ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” ์ตœ์ข…์ ์ธ BFS์˜ ํƒ์ƒ‰ ์ˆœ์„œ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘ ๋ฐฉ์‹..

kodo_o
'โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก