Algorithm/BOJ
2022. 3. 12.
[BOJ] ์ด์ง ํธ๋ฆฌ(13325)
[๋ฐฑ์ค(BOJ)] ์ด์ง ํธ๋ฆฌ(13325) C++ ๋ฌธ์ : BOJ_13325๋ฒ ์ด์ง ํธ๋ฆฌ ๋ฌธ์ ์ค๋ช
ํธ๋ฆฌ ์ํ ํฌํ์ด์ง ํธ๋ฆฌ๋ฅผ ๋ค๋ฃจ๋ ๋ฌธ์ ์
๋๋ค. ํธ๋ฆฌ์ ๋์ด k๊ฐ ์ฃผ์ด์ง๊ณ , ๋ณดํต์ ํธ๋ฆฌ ๋ฌธ์ ์๋ ๋ค๋ฅด๊ฒ ๋
ธ๋์ ๊ฐ์ด ์๋ ๊ฐ์ ์ ๊ฐ์ด ์ฃผ์ด์ง๋๋ค. ๋ฃจํธ ๋
ธ๋์์ ๋ฆฌํ ๋
ธ๋๋ก ๊ฐ๋ ๊ฑฐ๋ฆฌ ์ค ์ต๋๊ฐ์ x๋ผ๊ณ ํ๋ค๋ฉด, ๊ฐ๊ฐ์ ๊ฐ์ ์ ์ต์๊ฐ์ ๋ํ์ฌ ๋ฃจํธ ๋
ธ๋์์ ๋ฆฌํ ๋
ธ๋๊น์ง์ ๊ฐ๊ฐ์ ๋ชจ๋ ๊ฑฐ๋ฆฌ๋ฅผ x๋ฅผ ๋ง์ถฐ์ค์ผ ํ๋ ๋ฌธ์ ์
๋๋ค. Solution ๊ฑฐ๋ฆฌ๋ฅผ ๋ง์ถ ๋ ์์ ๋
ธ๋์ ๊ฐ์ ์์ ๊ฐ์ ์ต๋๊ฐ์ผ๋ก ๋ํด์ค์๋ก ์ต์ข
๊ฑฐ๋ฆฌ๋ค์ ๊ฐ์ด ์ค์ด๋ญ๋๋ค. ์ฌ๊ท์ ๋ฐฉ์์ ์ด์ฉํ์ต๋๋ค. ์ฐ์ dfs๋ฅผ ์ํํ์ฌ ๊ฐ์ฅ ๋จผ ๋ฆฌํ ๋
ธ๋์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํฉ๋๋ค ๊ทธ๋ฆฌ๊ณ ๋ค์ ๋ฆฌํ ๋
ธ๋๋ฅผ ์ํํฉ๋๋ค. ์ด๋, ๋ฆฌํ ๋
ธ๋๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๊ฒ ๋ง์ถ๊ธฐ ์ํด ..