๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๊ทธ๋ž˜ํ”„2

[Java] Graph (Adjacency Matrix, Adjacency List) ์ •์ (Vertex)๊ณผ ๊ฐ„์„ (Edge)๋กœ ๊ตฌ์„ฑ๋œ ๊ฒƒ, Graph(G) = (Vertex(V), Edge(E)) Graph ์šฉ์–ด ์ •์ (Vertex) - ๋…ธ๋“œ, ํŠน์ •ํ•  ์ˆ˜ ์žˆ๋Š” ์‹ค์ฒด๊ฐ„์„ (Edge) - ์ •์  ๊ฐ„ ์ด์–ด์ ธ ์žˆ๋Š” ์„ ๊ฐ€์ค‘์น˜(Weight) - ์ •์  ๊ฐ„์— ๊ฑฐ๋ฆฌ, ๋น„์šฉ (๊ฐ„์„ ์˜ ๊ธธ์ด๋ผ๊ณ  ์ƒ๊ฐํ•ด๋„ ์ข‹์Œ)๊ฒฝ๋กœ(Path) - ์ถœ๋ฐœ ์ •์ ์—์„œ ๋„์ฐฉ ์ •์ ๊นŒ์ง€์˜ ๊ฑฐ์ณ ๊ฐ„ ์ˆœ์„œ์ˆœํ™˜(Cycle) - ๊ฒฝ๋กœ์˜ ์ถœ๋ฐœ ์ •์ ๊ณผ ๋„์ฐฉ ์ •์ ์ด ๊ฐ™์€ ๊ฒฝ์šฐ์ฐจ์ˆ˜(Degree) - ์ •์ ์— ๋ถ™์€ ๊ฐ„์„  ์ˆ˜์ง„์ž… ์ฐจ์ˆ˜(In-Degree) - ์ •์ ์œผ๋กœ ๋“ค์–ด์˜ค๋Š” ๊ฐ„์„  ์ˆ˜์ง„์ถœ ์ฐจ์ˆ˜(Out-Degree) - ์ •์ ์—์„œ ๋‚˜๊ฐ€๋Š” ๊ฐ„์„  ์ˆ˜Graph ์ข…๋ฅ˜ ์œ ํ–ฅ ๊ทธ๋ž˜ํ”„(Directed Graph) - ํŠน์ • ์ •์ ์—์„œ ํŠน์ • ์ •์ ์œผ๋กœ ์ด๋™ํ•˜๋Š” ๊ทธ๋ž˜ํ”„๋ฌดํ–ฅ ๊ทธ๋ž˜ํ”„(UnDire.. 2024. 7. 9.
1. ์ž๋ฃŒ๊ตฌ์กฐ๋ž€? Data Structure ์ปดํ“จํ„ฐ๋Š” Data์˜ ์ง‘ํ•ฉ์ฒด์ž…๋‹ˆ๋‹ค. ์ปดํ“จํ„ฐ์—์„œ Data๋ฅผ ๋‹ค๋ฃจ๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์ด ์žˆ๊ฒ ์ฃ ? ์‹ค์ œ๋กœ ์‚ฌ๋žŒ์ด ์ƒ๊ฐํ•˜๊ธฐ์— ์ง๊ด€์ ์ด๊ฑฐ๋‚˜ ์ˆ˜ํ•™์ , ๋…ผ๋ฆฌ์ ์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์‚ฌ๊ณ ๋ฅผ ์ปดํ“จํ„ฐ์˜ ์ž…์žฅ์—์„œ ํ‘œํ˜„ํ•œ ๊ฒƒ์ด ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์ปดํ“จํ„ฐ๋Š” ์‚ฌ๋žŒ๊ณผ ๋‹ค๋ฅด๊ฒŒ ์ƒ๊ฐ์„ ํ•  ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋„๋ก '๋ช…๋ น'์„ ํ•ด์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. How ? ์–ด๋–ป๊ฒŒ ์ปดํ“จํ„ฐ์—๊ฒŒ ๋ช…๋ น์„ ํ•ด์•ผ ํ• ๊นŒ์š”? ๊ธฐ๋ณธ์ ์œผ๋กœ ์ปดํ“จํ„ฐ๋Š” ๋ณ€์ˆ˜์— ๊ฐ’์„ ํ• ๋‹นํ•˜๊ณ  ์ž…, ์ถœ๋ ฅ์„ ํ†ตํ•ด ์šฐ๋ฆฌ๊ฐ€ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋•Œ, 1, 2, 3, 4, 5, 7 ์ด ์žˆ์„ ๋•Œ '6'์„ ์ถ”๊ฐ€ํ•˜๋Š”๋ฐ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ์ฆ‰, ๊ฒฐ๊ณผ๋ฅผ 1 2 3 4 5 6 7๋กœ ๋‚˜ํƒ€๋‚ด๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ๋ฐฉ๋ฒ•์€ ๋ฌด์ˆ˜ํžˆ ๋งŽ์€๋ฐ์š”. vector arr = {1, 2, 3, 4, 5, 7};.. 2024. 1. 26.