์ฝ๋ฉํ
์คํธ/๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ
2022. 2. 20.
๋๋น ์ฐ์ ํ์(BFS)
BFS(๋๋น ์ฐ์ ํ์) 1. BFS(Breadth-First Search)๋? BFS์๊ณ ๋ฆฌ์ฆ์ ๋๋น ์ฐ์ ํ์์ด๋ ์๋ฏธ๋ฅผ ๊ฐ์ง๋ค. ์ด๋ ๊ฐ๊น์ด ๋
ธ๋๋ถํฐ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ ๋ป์ด๋ค. DFS๋ ์ต๋ํ ๋ฉ๋ฆฌ์๋(๊น์) ๋
ธ๋๋ถํฐ ํ์ํ๋๊ฒ์ ๋นํด BFS๋ ๊ฐ๊น์ด ๋
ธ๋๋ถํฐ ํ์ํ๋ฏ๋ก ์ด ๋๊ฐ๋ฅผ ์ ์ ํ๊ฒ ์ฌ์ฉํด์ผ ํ๋ค. BFS ๊ตฌํ์์๋ ์ ์
์ ์ถ, ์ฆ ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ๋๊ฒ์ด ์ ์์ด๋ค. BFS ์๊ณ ๋ฆฌ์ฆ์ ๋์๋ฐฉ์์๋ 1. ํ์ ์์ ๋
ธ๋๋ฅผ ํ์ ์ฝ์
ํ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ๋ฅผ ํ๋ค. 2. ํ์์ ๋
ธ๋๋ฅผ ๊บผ๋ด ํด๋น ๋
ธ๋์ ์ธ์ ๋
ธ๋ ์ค์์ ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๋ฅผ ๋ชจ๋ ํ์ ์ฝ์
ํ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ๋ฅผ ํ๋ค. 3. 2๋ฒ์ ๊ณผ์ ์ ๋ ์ด์ ์ํํ ์ ์์ ๋๊น์ง ๋ฐ๋ณตํ๋ค. 2. ์์ ์ฝ๋ from collections import d..