์ ์ฅ ํธ๋ฆฌ (Spanning Tree) ๊ทธ๋ํ์์ ๋ชจ๋ ๋ ธ๋๋ฅผ ํฌํจํ๋ฉด์ ์ฌ์ดํด์ด ์กด์ฌํ์ง ์๋ ๋ถ๋ถ ๊ทธ๋ํ๋ฅผ ์๋ฏธํ๋ค. ๋ชจ๋ ๋ ธ๋๊ฐ ํฌํจ๋์ด ์๋ก ์ฐ๊ฒฐ๋๋ฉด์ ์ฌ์ดํด์ด ์กด์ฌํ์ง ์๋๋ค๋ ์กฐ๊ฑด์ ํธ๋ฆฌ์ ์กฐ๊ฑด์ด๊ธฐ๋ ํ๋ค. ์ ์ฅ ํธ๋ฆฌ ์ฌ์ฉ ๋ชฉ์ ๋ชจ๋ ๋ ธ๋๊ฐ ์ฐ๊ฒฐ๋์ด ์์ง๋ง ์ผ๋ถ ๊ฐ์ ์ ์ฌ์ฉํ์ง ์์๋ ๋๋ค๋ ์ ์์ ์ค์ ๋ฌธ์ ์ํฉ์์ ํจ๊ณผ์ ์ผ๋ก ์ฌ์ฉ๋ ์ ์๋ค. ์ต์ ์ ์ฅ ํธ๋ฆฌ (MST, Minimum Spanning Tree) ์ต์ํ์ ๋น์ฉ์ผ๋ก ๊ตฌ์ฑ๋๋ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ์์ผ ํ ๋ ์ด๋ป๊ฒ ํด์ผ ํ ๊น์? ์๋ฅผ ๋ค์ด N๊ฐ์ ๋์๊ฐ ์กด์ฌํ๋ ์ํฉ์์ ๋ ๋์ ์ฌ์ด์ ๋๋ก๋ฅผ ๋์ ์ ์ฒด ๋์๊ฐ ์๋ก ์ฐ๊ฒฐ๋ ์ ์๊ฒ ๋๋ก๋ฅผ ์ค์นํ๋ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ด ์๋ค. ๋ ๋์ A, B๋ฅผ ์ ํํ์ ๋ A์์ B๋ก ์ด๋ํ๋ ๊ฒฝ๋ก๊ฐ ๋ฐ๋..
