[c++] BOJ 4195 :: ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ
Algorithm ๋ฌธ์ œ/BOJ 2021. 9. 28. 19:49

๋ฌธ์ œ ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ ๋ฏผํ˜์ด๋Š” ์†Œ์…œ ๋„คํŠธ์›Œํฌ ์‚ฌ์ดํŠธ์—์„œ ์นœ๊ตฌ๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒƒ์„ ์ข‹์•„ํ•˜๋Š” ์นœ๊ตฌ์ด๋‹ค. ์šฐํ‘œ๋ฅผ ๋ชจ์œผ๋Š” ์ทจ๋ฏธ๊ฐ€ ์žˆ๋“ฏ์ด, ๋ฏผํ˜์ด๋Š” ์†Œ์…œ ๋„คํŠธ์›Œํฌ ์‚ฌ์ดํŠธ์—์„œ ์นœ๊ตฌ๋ฅผ ๋ชจ์œผ๋Š” ๊ฒƒ์ด ์ทจ๋ฏธ์ด๋‹ค. ์–ด๋–ค ์‚ฌ์ดํŠธ์˜ ์นœ๊ตฌ ๊ด€๊ณ„๊ฐ€ ์ƒ๊ธด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋‘ ์‚ฌ๋žŒ์˜ ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ์— ๋ช‡ ๋ช…์ด ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์นœ๊ตฌ ๋„คํŠธ์›Œํฌ๋ž€ ์นœ๊ตฌ ๊ด€๊ณ„๋งŒ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์‚ฌ์ด๋ฅผ ๋งํ•œ๋‹ค. ํ’€์ด ํŠน์ • ์ด๋ฆ„์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ํ•ด๋‹น ์ด๋ฆ„์ด ์†ํ•œ ๊ทธ๋ฃน์„ ์•Œ ์ˆ˜ ์žˆ์–ด์•ผ ํ•˜๊ณ , ํ•ด๋‹น ๊ทธ๋ฃน์— ์žˆ๋Š” ์ด๋ฆ„์˜ ๊ฐœ์ˆ˜๋ฅผ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ด๋ฆ„์ด ์†ํ•œ ๊ทธ๋ฃน์„ ๋ฐ”๋กœ ์ฐพ๊ธฐ ์œ„ํ•ด์„œ๋Š” map๋ฅผ ์ด์šฉํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ ํ•ด๋‹น ๊ทธ๋ฃน์— ์žˆ๋Š” ์ด๋ฆ„์˜ ๊ฐœ์ˆ˜๋ฅผ ํŒŒ์•…ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„์ด ๊ฐ€๋Šฅํ•˜๋‹ค. set group[..