[๋ฐฑ์ค€] 1717. ์ง‘ํ•ฉ์˜ ํ‘œํ˜„/Python - Gold5
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/1717์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 77876 KB, ์‹œ๊ฐ„: 284 ms๋ถ„๋ฅ˜์ž๋ฃŒ ๊ตฌ์กฐ, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ๋ฌธ์ œ ์„ค๋ช…์ดˆ๊ธฐ์— n+1n+1๊ฐœ์˜ ์ง‘ํ•ฉ {0},{1},{2},…,{n}{0},{1},{2},…,{n}์ด ์žˆ๋‹ค. ์—ฌ๊ธฐ์— ํ•ฉ์ง‘ํ•ฉ ์—ฐ์‚ฐ๊ณผ, ๋‘ ์›์†Œ๊ฐ€ ๊ฐ™์€ ์ง‘ํ•ฉ์— ํฌํ•จ๋˜์–ด ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธํ•˜๋Š” ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.์ง‘ํ•ฉ์„ ํ‘œํ˜„ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.โœ๐Ÿปํ’€์ดhttps://yoongrammer.tistory.com/102 ์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Set) & ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ(Union find)๋ชฉ์ฐจ์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Set) & ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ(Union find)์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Set)Disjoint Set(์„œ๋กœ์†Œ ์ง‘ํ•ฉ, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ)์ด๋ž€ ์„œ๋กœ..