โ๏ธ ์๊ณ ๋ฆฌ์ฆ/Graph
Dijsktra (๋ค์ต์คํธ๋ผ) ์ต๋จ ๊ฒฝ๋ก ํ์ - 1 ์ ๋ง ์ค๋๋ง์ ํฌ์คํ
์ด๋ค. ์๋ ๋ชฉํ๋๋ก ์งํํ์ผ๋ฉด ๊ฐ๊ฐ์ ํ๊ธฐ ์ ์ DP๊น์ง ํฌ์คํ
์ ํ์ด์ผํ๋๋ฐ ์์ ์กฐ๊ธ ๋ฐ๋นด๋ค...(์ฌ์ค ์์์ด ์๋๊ฑธ ์๋...) ์๋ฌดํผ ์ด๋ฒ 3-1 ๊ณผ๋ชฉ์ ์๊ณ ๋ฆฌ์ฆ ์์ฉ์ด๋ผ๋ ๊ณผ๋ชฉ์ ์๊ฐํ๋๋ฐ ์๋
์๋ ๋ฅ๋ฌ๋๊ณผ ๊ด๋ จํ์ฌ ์์
ํ๋ค๊ณ ํด์ ์ ์ฒญํ๋๋ฐ ์ด๋ฒ์ ๊ต์๋์ด ๋ฐ๋๋ฉด์ ์ ๋ง ์๊ณ ๋ฆฌ์ฆ์ ๋ํด ํ์ตํ๋ ์์
์ด ๋์ด๋ฒ๋ ธ๋ค. ์ด์ง ์์ฌ์ ์ง๋ง ๊ฐ์๊ณํ์๋ฅผ ๋ณด๋ 2-2 ์๊ณ ๋ฆฌ์ฆ ์์
๊ณผ ๊ฑฐ์ ๋น์ทํด์? ํ๊ธฐ ์ด์ ๋ฏธ๋ฆฌ๋ฏธ๋ฆฌ ์ ๋ฆฌํด๋๋ ค๊ณ ํ๋ค. ์๋ก ์ด ๊ธธ์๋ค. ๋ค์ต์คํธ๋ผ๋ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ค์๊ณผ ๊ฐ์ ๊ทธ๋ํ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ํ์ํด๋ณด์. graph ๋ณ์์ ์ฐ๊ฒฐ๋ ์ ์ ๊ณผ ๊ฐ์ค์น๊ฐ ์ ์ฅ๋์ด ์๋ค๊ณ ๋ณธ๋ค. graph[1] = [2..
โ๏ธ ์๊ณ ๋ฆฌ์ฆ/Graph
DFS(Depth-Find-Search) ๊น์ด ์ฐ์ ํ์ ์ง๋ ์๊ฐ BFS์ ์ด์ด ์ค๋์ DFS์ ๋ํด ์์๋ณด๋ ค๊ณ ํ๋ค. DFS๋ Depth-Find-Search๋ก ๊น์ด ์ฐ์ ํ์์ด๋ค. BFS์ ๋ค๋ฅด๊ฒ DFS๋ ๊น์ด๋ฅผ ์ฐ์ ์ ์ผ๋ก ํ์ํ๋ค. ์ฆ ์ต๋ ๊น์ด๊น์ง ์ฌ๊ท์ ์ผ๋ก ์ด๋ํ ํ ์ต๋ ๊น์ด์ ๋๋ฌํ ๊ฒฝ์ฐ ์์ผ๋ก ์ด๋ํ๋ค. ๋ํ BFS์์๋ Queue๋ฅผ ์ฌ์ฉํ๋ค๋ฉด DFS์์๋ Stack์ ์ฌ์ฉํ๋ค. ์ด Stack์ ์ ์ฅ๋ ๊ฐ์ด ์ฐ๋ฆฌ๊ฐ ์ํ๋ DFS์ ํ์ ์์์ด๋ค. ์๊ณ ๋ฆฌ์ฆ ๋์ ๋ฐฉ์ ๋ค์๊ณผ ๊ฐ๋ค. 1. ํน์ ์ ์ ์ด ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ธ ๊ฒฝ์ฐ ์ด๋ฅผ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํด์ค๋ค. 2. ํด๋น ์ ์ ๊ณผ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ ์ ์ ๋ํด ์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค. ๋ค์๊ณผ ๊ฐ์ ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ก์ ๋ DFS๋ฅผ ์ ์ฉํด๋ณด์. โ ์์ ์ ์ ์ 8..
โ๏ธ ์๊ณ ๋ฆฌ์ฆ/Graph
BFS(Breath-Find-Search) ๋๋น ์ฐ์ ํ์ ๊ทธ๋ํ์ ํ์ ๋ฐฉ๋ฒ ์ค ํ๋์ BFS์ ๋ํด์ ์ดํด๋ณด๋ ค๊ณ ํ๋ค. BFS๋ ๋ง ๊ทธ๋๋ก ๋๋น ์ฐ์ ํ์, ์ฆ ํน์ Vertice์์ ๊ฐ์ฅ ๊ฐ๊น์ด Vertice๋ถํฐ ํ์ํ๋ค๋ ๋ป์ด๋ค. ์ฐ์ BFS๋ฅผ ์ฌ์ฉํ๊ธฐ ์ํด์๋ Queue๊ฐ ํ์ํ๋ค. Stack, Queue, Heap์ ๋ํด์๋ ๋์ค์ ์์ธํ ์ค๋ช
ํ๊ธฐ๋ก ํ๊ณ Queue์ ๋ํด ๊ฐ๋จํ๊ฒ ์ค๋ช
ํ์๋ฉด FIFO(First in First out - ์ ์
์ ์ถ)์ผ๋ก ๋์ํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ์์์๋ ๋งํ๋ฏ์ด BFS์ ๊ฐ์ฅ ํฐ ๊ฐ๋
์ ๊ฐ๊น์ด ์ ์ ์ ๋ฐฉ๋ฌธํ๋, ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ธ ๊ฒฝ์ฐ ๋ฐฉ๋ฌธ ๋ฆฌ์คํธ์ ์ ์ ์ ์ ์ฅํ๋ฉด ๋๋ค. ์ด ๋ฐฉ๋ฌธ ๋ฆฌ์คํธ๊ฐ ์ฐ๋ฆฌ๊ฐ ์ํ๋ ์ต์ข
์ ์ธ BFS์ ํ์ ์์์ด๋ค. ์๊ณ ๋ฆฌ์ฆ ๋์ ๋ฐฉ์..