boj 16965 1
๋ฐฑ์ค€ 16965

๋ฌธ์ œ๋”๋ณด๊ธฐ์ „์ฒด ์ฟผ๋ฆฌ์˜ ์ˆ˜(๊ตฌ๊ฐ„์˜ ์ตœ๋Œ€ ์ˆ˜)๊ฐ€ 100 ์ดํ•˜๋ผ๋Š” ์ „์ œ๋กœ ๋ชจ๋“  ๊ตฌ๊ฐ„์— ๋Œ€ํ•œ BFS๋ฅผ ์ง„ํ–‰ํ•จ์œผ๋กœ์„œ ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.UnionFind๋กœ ํ’€์ดํ•˜๋‹ค ์‹คํŒจํ–ˆ๋Š”๋ฐ, ๊ตฌ๊ฐ„์˜ ์ˆœ์„œ๊ฐ€ ๊ตฌ๊ฐ„์˜ ํฌํ•จ ์—ฌ๋ถ€์— ์˜ํ–ฅ์„ ๋ฏธ์น˜๋ฏ€๋กœ ๋ชจ๋“  ๊ตฌ๊ฐ„์˜ ํฌํ•จ ๊ด€๊ณ„๊ฐ€ ๊ฐฑ์‹ ๋˜์—ˆ์„๋•Œ ๊ฐ๊ฐ์˜ ํฌํ•จ๋œ ๊ตฌ๊ฐ„์— ๋Œ€ํ•œ UnionFind๋ฅผ ๋‹ค์‹œ ์ˆ˜ํ–‰ํ•ด์ค˜์•ผ ์ด ๋ฌธ์ œ๋ฅผ ํ’€์ดํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๋‹จ์ˆœํ•œ BFS๋กœ ๋ฌธ์ œ๋ฅผ ์žฌ๊ตฌ์„ฑํ–ˆ๋‹ค. ๊ฒฐ๊ตญ ์™„์ „ํƒ์ƒ‰์œผ๋กœ ํ’€์ดํ•ด์•ผํ•˜๋ฏ€๋กœ 2 a b์— ๋Œ€ํ•œ ์ž…๋ ฅ์ด ์™”์„๋•Œ a ๊ตฌ๊ฐ„์—์„œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ตฌ๊ฐ„์— ๋Œ€ํ•ด ํƒ์ƒ‰ํ•˜๋ฉด์„œ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ตฌ๊ฐ„์„ ๊ธฐ์ค€์œผ๋กœ ๋‹ค์‹œ BFS๋ฅผ ์ง„ํ–‰ํ•˜์—ฌ ๊ฒฐ๊ตญ b ๊ตฌ๊ฐ„์ด ๋‚˜์˜ค๋Š”์ง€์— ๋Œ€ํ•œ ์—ฌ๋ถ€๋งŒ ํ™•์ธํ•˜๋ฉด ๋œ๋‹ค.๊ตฌ๊ฐ„์˜ ์ˆ˜๋ฅผ N์ด๋ผ ํ•˜๊ณ , 2 a b๋ผ๋Š” ์ฟผ๋ฆฌ๊ฐ€ ์˜ค๋Š” ๊ฒฝ์šฐ๋ฅผ M์ด๋ผ ํ• ..
algorithm 2024.07.30
1
๋”๋ณด๊ธฐ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”