์ฝ๋ฉํ
์คํธ/๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ
2022. 2. 24.
์ต๋จ ๊ฒฝ๋ก (simple_dijkstra)
simple_dijkstra (๊ฐ๋จํ ๋ค์ต์คํธ๋ผ) ์ฌ๋ฌ ๋
ธ๋๊ฐ ์์ ๋, ์ธก์ ํ ๋
ธ๋์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋
ธ๋๋ก ๊ฐ๋ ๊ฐ๊ฐ์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํด์ฃผ๋ ์๊ณ ๋ฆฌ์ฆ (์์ ๊ฐ์ )์ด ์์๋ ์ ์์ ์ผ๋ก ์๋ํ๋ค. ๊ทธ๋์ ํ์ค์ธ๊ณ์ ๊ธธ์ ํ ๋๋ก gps๋ฑ์ ์ฃผ๋ก ์ฐ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๊ธฐ๋ณธ์ ์ผ๋ก ๊ฐ์ฅ ๋น์ฉ์ด ์ ์ ๋
ธ๋๋ฅผ ์ฐพ์ ๊ฐฑ์ ํ๋ฏ๋ก ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋ถ๋ฅ๋๋ค ์๊ณ ๋ฆฌ์ฆ์ ์๋ฆฌ๋ก๋ ์ถ๋ฐ ๋
ธ๋๋ฅผ ์ค์ ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ์ด๊ธฐํ ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋๋ฅผ ์ ํ ํด๋น ๋
ธ๋๋ฅผ ๊ฑฐ์ณ ๋ค๋ฅธ ๋
ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ ๊ณ์ฐํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ ๊ฐฑ์ ์ ๊ณผ์ ์์ 3๊ณผ 4๋ฅผ ๋ฐ๋ณต ํ๋จ๊ณ๋ฅผ ์๋ฃํ๋ฉด ๊ทธ ๋จ๊ณ์ ๋
ธ๋๋ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ํ์คํ ๊ตฌํด์ง๊ฒ์ด๋ค. ๊ฐ๋จํ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ O(v^2)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ฐ ์ด๋ ..