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

backtracking1

[Python] DFS & BFS ๊ทธ๋ž˜ํ”„๋‚˜ ํŠธ๋ฆฌ ๊ตฌ์กฐ์— ๋Œ€ํ•ด์„œ ์ถฉ๋ถ„ํ•œ ์„ค๋ช…์ด ์žˆ๋Š” ๊ธ€์€ ์•„๋‹™๋‹ˆ๋‹ค. python ์œผ๋กœ DFS , BFS ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๊ฐ„๋‹จํ•œ ์ฝ”๋“œ์™€ ๊ทธ์— ๋Œ€ํ•œ ๊ฐœ๋…์„ ์ •๋ฆฌํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”„๋ž€? - ์‚ฌ์šฉ ์ง€๋„, ๋„ค์ด๊ฒŒ์ด์…˜์— ์“ฐ์ž„ SNS, ๋ฉ”์‹ ์ €(ํŒ”๋กœ์šฐ/์–ธํŒ”๋กœ์šฐ) ๊นƒ VCS ์— ์“ฐ์ž„ - ์ •์ (vertext == node) ๊ณผ ๊ฐ„์„ (edge)๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Œ. - ๊ตฌ๋ถ„ 1. ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(==์–‘๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„) 2. ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ -------------------------------- 1. ์ˆœํ™˜ ๊ทธ๋ž˜ํ”„ 2. ๋น„์ˆœํ™˜ ๊ทธ๋ž˜ํ”„ ๋ฐฉํ–ฅ์„ฑ ๋น„์ˆœํ™˜ ๊ทธ๋ž˜ํ”„(DAG) Directed Acyclic Graph - ์—ฐ๊ฒฐ์š”์†Œ ํŠธ๋ฆฌ๋ž€? - ์ˆœํ™˜์„ฑX, ๋ฌด๋ฐฉํ–ฅ - ๋ฃจํŠธ ๋…ธ๋“œ, ๋ฆฌํ”„ ๋…ธ๋“œ - ๋…ธ๋“œ A์—์„œ ๋…ธ๋“œ B๋กœ ๊ฐ€๋Š” ๊ฒฝ๋กœ๋Š” ๋ฐ˜๋“œ์‹œ ์กด์žฌํ•˜๋ฉฐ ์œ ์ผํ•˜๋‹ค. ๊ทธ.. 2021. 5. 12.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”