โ ๋ฐฑ์ค 1043 ๊ฑฐ์ง๋ง — ํต์ฌ ํ๋ฆ
๐ ๋ฌธ์ ํต์ฌ
- ํํฐ์ ์ง์ค ์๋ ์ฌ๋์ด ์์ผ๋ฉด ๊ฑฐ์ง๋ง ๋ชป ํจ
- ํํฐ๊ฐ ๊ฒน์น๋ฉด ์ง์ค์ด ํผ์ง → ๊ทธ๋ฃน ๊ด๋ฆฌ ํ์
๐ ํต์ฌ ์์ด๋์ด
1๏ธโฃ ๊ฐ์ ํํฐ๋ฉด ๊ฐ์ ๊ทธ๋ฃน
→ ์ฐธ์์๋ผ๋ฆฌ union ์ผ๋ก ์ฐ๊ฒฐ
2๏ธโฃ ์ง์ค ์๋ ์ฌ๋๋ค๋ ๊ฐ์ ๊ทธ๋ฃน์ผ๋ก ๋ฌถ๊ธฐ
3๏ธโฃ ํ๋ณ์ find๋ก!
→ ํํฐ์ ๋ฃจํธ == ์ง์ค ๊ทธ๋ฃน ๋ฃจํธ๋ฉด ๊ฑฐ์ง๋ง X
๐ ํ๋ฆ ์ ๋ฆฌ
โ ํํฐ๋ณ ์ฐธ์์ → union
โ ์ง์ค ์๋ ์ฌ๋๋ค → union
โ ํํฐ ๋๋ฉด์ → ํํฐ์ find → ์ง์ค ๋ฃจํธ๋ ๋ค๋ฅด๋ฉด ๊ฑฐ์ง๋ง O
๋ฐ์ํ
'๐ Algorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| โ BOJ 17070 - 3์ฐจ์ DP (0) | 2025.07.03 |
|---|---|
| โ BOJ 15686 - ์กฐํฉ ๋ฐฑํธ๋ํน (0) | 2025.07.02 |
| โ BOJ 1918 - ์คํ (0) | 2025.07.01 |
| [์ฝํ ] 2206 - ํผ๋ณด๋์น ํ๋ ฌ์ฐ์ฐ (0) | 2025.06.28 |
| โ BOJ 1865 - ๋ฒจ๋งํฌ๋ (0) | 2025.06.27 |