๋ชฉ๋กํŠธ๋ฆฌ์˜ ๋„ˆ๋น„ (1)

Hello Ocean! ๐ŸŒผ

[๋ฐฑ์ค€/C++] 2250. ํŠธ๋ฆฌ์˜ ๋†’์ด์™€ ๋„ˆ๋น„

๋ฌธ์ œ https://www.acmicpc.net/problem/2250 ์ž…๋ ฅ๋œ ์ด์ง„ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ ๊ฐ ๋…ธ๋“œ์— ๋Œ€ํ•ด ์„ธ๋กœ์œ„์น˜(์—ด)๋ฒˆํ˜ธ๋ฅผ ๋งค๊ฒจ์„œ ๊ฐ€์žฅ ๋„“์€ ๋ ˆ๋ฒจ์„ ์ฐพ๊ณ , ๊ทธ ๋„ˆ๋น„๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ํ’€์ด left, rignt๊ฐ’์„ ๊ฐ€์ง„ ๋…ธ๋“œ๋ฅผ ๋งŒ๋“ค๊ณ , ๋…ธ๋“œ๋ฒˆํ˜ธ๊ฐ€ 0~N-1๊นŒ์ง€์ด๊ธฐ ๋•Œ๋ฌธ์— Nํฌ๊ธฐ์˜ ๋…ธ๋“œ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ํŠธ๋ฆฌ๋กœ ์ด์šฉํ–ˆ๋‹ค. -> ๋ฃจํŠธ๋ฅผ ์•Œ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์—, ์ž…๋ ฅ๋ฐ›์„ ๋•Œ check๋ฐฐ์—ด์— ์ž์‹ ,์™ผ์ชฝ์ž์‹,์˜ค๋ฅธ์ชฝ์ž์‹ ๋ชจ๋‘ +1์„ ํ–ˆ๋‹ค. ์ž…๋ ฅ์„ ๋‹ค ๋ฐ›์€ ํ›„์— check[root] = 1์ด๊ณ  , root๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๋Š” 2์ด๋‹ค. ์ด๋ ‡๊ฒŒ ๋ฃจํŠธ๋ฅผ ์ฐพ์•˜๋‹ค. ์ค‘์œ„์ˆœํšŒ : ์™ผ->์ž์‹ ->์˜ค ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธ ๋”ฐ๋ผ์„œ ํŠธ๋ฆฌ๋ฅผ ์ค‘์œ„์ˆœํšŒํ•˜์—ฌ 1๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ์ฆ๊ฐ€์‹œํ‚ค๋ฉฐ ์—ด๋ฒˆํ˜ธ๋ฅผ ๋งค๊ฒผ๋‹ค. ์ด ๋•Œ, level๊ฐ’์„ ์ด์šฉํ•˜์—ฌ min_col..
Algorithm 2021. 6. 2. 21:40
์ด์ „ Prev 1 Next ๋‹ค์Œ