![](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbkODzh%2FbtqYDjV8FTF%2FSosRatpNY97k5YoqACRNR0%2Fimg.png)
ํฉ์น ํ์ ์๊ธ ๋์ด๋ : โ โ โ โโ ๊ฑธ๋ฆฐ ์๊ฐ : ๋ชป ํ์์ ๋ฌธ์ ํฉ์น ํ์ ์๊ธ ๋งํฌ ํด์ค ๊ทธ๋ํ ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ dijkstra๋ floyd-warshal ์๊ณ ๋ฆฌ์ฆ ์ด์ฉ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ ๋ชจ๋ ์ ์ => ๋ชจ๋ ์ ์ ์ต๋จ ๊ฒฝ๋ก ๊ตฌํ๊ธฐ d[i][j] = i๋ถํฐ j๊น์ง์ ์ต์ ํ์ ์๊ธ min(d[s][k]+d[k][a]+d[k][b])๋ฅผ ๊ตฌํ๋ฉด ๋จ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ํ ์ ์ => ๋ชจ๋ ์ ์ ์ต๋จ ๊ฒฝ๋ก ๊ตฌํ๊ธฐ ๋ฐฐ์ด(dist)๊ณผ ์ฐ์ ์์ ํ(qp)๋ฅผ ์ด์ฉํด์ ์ฒซ ์ ์ ๋ถํฐ ๊ฐ ๋ ธ๋๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ฐฐ์ด์ ์ ๋ฐ์ดํธํ๋ ๋ฐฉ์ ์ฐ์ ์์ ํ์ ๋ค์ ๊ฐ ์ ์๋ ๋ ธ๋๋ค์ ๋ฃ์ผ๋ฉด์ ํด๋น ๊ฑฐ๋ฆฌ๋ฅผ dist ๋ฐฐ์ด์์ ๊ฐฑ์ ํ๋ ๋ฐฉ์ a, b ๊ฐ๊ฐ์ ์ต๋จ ๊ฑฐ๋ฆฌ ๋น์ฉ๊ณผ ํน์ ์ง์ ๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ ๋น์ฉ ์ค ๊ฐ์ฅ ์์ ๊ฒ์ ..
![](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FpKSVC%2FbtqWVQ9jU1H%2FhYqG0kJ2jLkce0vuPhvEL1%2Fimg.png)
๋ฉ๋ด ๋ฆฌ๋ด์ผ ๋์ด๋ : โ โ โโโ ๊ฑธ๋ฆฐ ์๊ฐ : 50๋ถ ๋ฌธ์ ๋ฉ๋ด ๋ฆฌ๋ด์ผ ๋ฌธ์ ๋ฐ๋ก๊ฐ๊ธฐ ๋ฌธ์ ์ค๋ช ๋ ์คํ ๋์ ์ด์ํ๋ ์ค์นดํผ๋ ์ฝ๋ก๋19๋ก ์ธํ ๋ถ๊ฒฝ๊ธฐ๋ฅผ ๊ทน๋ณตํ๊ณ ์ ๋ฉ๋ด๋ฅผ ์๋ก ๊ตฌ์ฑํ๋ ค๊ณ ๊ณ ๋ฏผํ๊ณ ์์ต๋๋ค. ๊ธฐ์กด์๋ ๋จํ์ผ๋ก๋ง ์ ๊ณตํ๋ ๋ฉ๋ด๋ฅผ ์กฐํฉํด์ ์ฝ์ค์๋ฆฌ ํํ๋ก ์ฌ๊ตฌ์ฑํด์ ์๋ก์ด ๋ฉ๋ด๋ฅผ ์ ๊ณตํ๊ธฐ๋ก ๊ฒฐ์ ํ์ต๋๋ค. ์ด๋ค ๋จํ๋ฉ๋ด๋ค์ ์กฐํฉํด์ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๋ฉด ์ข์ ์ง ๊ณ ๋ฏผํ๋ ์ค์นดํผ๋ ์ด์ ์ ๊ฐ ์๋๋ค์ด ์ฃผ๋ฌธํ ๋ ๊ฐ์ฅ ๋ง์ด ํจ๊ป ์ฃผ๋ฌธํ ๋จํ๋ฉ๋ด๋ค์ ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๊ธฐ๋ก ํ์ต๋๋ค. ๋จ, ์ฝ์ค์๋ฆฌ ๋ฉ๋ด๋ ์ต์ 2๊ฐ์ง ์ด์์ ๋จํ๋ฉ๋ด๋ก ๊ตฌ์ฑํ๋ ค๊ณ ํฉ๋๋ค. ๋ํ, ์ต์ 2๋ช ์ด์์ ์๋์ผ๋ก๋ถํฐ ์ฃผ๋ฌธ๋ ๋จํ๋ฉ๋ด ์กฐํฉ์ ๋ํด์๋ง ์ฝ์ค์๋ฆฌ ๋ฉ๋ด ํ๋ณด์ ํฌํจํ๊ธฐ๋ก ํ์ต๋๋ค. ์๋ฅผ ๋ค์ด, ์๋ 6๋ช ์ด ์ฃผ..
Comment