2021. 9. 28. 23:08ใ๐ TIL
BFS ์ DFS
์์ฆ ์์นจ๋ง๋ค BFS/DFS ๋ฌธ์ ๋ฅผ ํ๋์ฉ ํ๊ณ ์๋ค. ์๋ ๋ชปํ๋ ์ ํ์ด๊ธฐ๋ ํ๊ณ , ์ฝ๋ฉ ํ ์คํธ๋ง๋ค ๋งค๋ฒ ๋งํ ๊ฐ์ธ์ ์ผ๋ก ๋ฒฝ์ด๋ผ ๋๊ผ๋ ๋ฌธ์ ์๋ค. ๊ทธ๋ฐ๋ฐ ์ด์ , ์ค๋์ ํ๋ก๊ทธ๋๋จธ์ค lv3 ๋ฌธ์ ๋ ํ๋ฒ๋ง์ ํ๋ฆฌ๋๊ฒ ์๋๊ฐ. ์ ๊น์ด์ง๋ง ๋น์ด ๋ณด์๋ค. ๊ทธ๋ฌ๋ฉด์ BFS / DFS ์ ์ฐจ์ด,BFS: queue, DFS: stack ์ ์ฒด๊ฐํ๋ค.
BFS ๋ ์์ ๊ณผ ์ฐ๊ฒฐ๋ ๋ ธ๋๋ฅผ ์ฐ์ ์ ์ผ๋ก ๋ชจ๋ ์ํํ๋๋ฐ, ์ด๋ฅผ queue ์ ๋ด๋๋ค. stack ์๋ ๋ด์ ์ ์์ง ์๋๊ณ ?
์๋ฐ์คํฌ๋ฆฝํธ for ๋ฌธ
์ด๊ฑฐ ์ฒ์ ์์๋ค. for () ๋ด๋ถ์์ in ๊ณผ of ์ ๋ฐ๋ผ ์ฐจ์ด๊ฐ ๋ฐ์ํ๋๋ฐ, in ์ ์ฌ์ฉํ๋ฉด ๋ฐฐ์ด(List)์ ์ธ๋ฑ์ค๋ก ์ ๊ทผ, of ๋ฅผ ์ฌ์ฉํ๋ฉด ๋ฐฐ์ด์ ์์์ ์ ๊ทผํ๋ค.
// index์ ์ ๊ทผ
for (let i in List){
...
}
// element ์ ์ ๊ทผ
for (let i of List){
...
}
ํ์ฌ
๋ฃจ๋ ์ค๋น ์ปดํฌ๋ํธ๊ฐ ํด๋์ค ์ปดํฌ๋ํธ๋ฅผ ๋ฒ ์ด์ค๋ก ๊ฐ๋ฐ๋๋ค ๋ณด๋, ํจ์ ์ปดํฌ๋ํธ๋ฅผ ์ฌ์ฉํ๋ ์ฐ๋ฆฌ ๋ถ์์์ ๋ฐ๋ก ์ฌ์ฉํ๊ธฐ ์ฝ์ง ์์๋ค. ์ง์์ ์ผ๋ก ์๋ฌ๊ฐ ๋ฐ์ํด์ ๊ณจ๋จธ๋ฆฌ๋ฅผ ์์๋๋ฐ, ์ ๋๋ค ์ฐ๊ตฌ์๋ถ์ด ์ฝ๋๋ฅผ ๊ณ์ ๊น๋ณธ๋ค๋๋ ์ค์ ๋ก ํด๊ฒฐ์ฑ ์ ๊ฐ์ ธ์ค์ จ๋ค. ์ง๊ธ๊น์ง ๋ ํผ์ ๋ฌด์ธ๊ฐ ํด๊ฒฐํด์ผํ๋ค๋ ๋ง์์ ๋ถ๋ด๊ฐ์ด ์ปธ๋๋ฐ, ๋ฏฟ์๋งํ ๋๋ฃ๊ฐ ์๊ธด ๊ธฐ๋ถ์ด ๋ค์๋ค. ์ด๊ฒ ์๊ฐ๋ณด๋ค ๋ ๋ ํด์ง๋ค. ์ต๊ณ ์ ๋ณต์ง๋ ๋๋ฃ๋ผ๋ ๋ง์ด ๊ดํ ๋์ค๋๊ฒ ์๋๊ฐ๋ณด๋ค.