๋ชฉ๋กLCA (1)

Hello Ocean! ๐ŸŒผ

[๋ฐฑ์ค€/C++] 11437, 11438. LCA 1,2

๋ฌธ์ œ https://www.acmicpc.net/problem/11437 -> LCA 1 https://www.acmicpc.net/problem/11438 -> LCA 2 ์ฃผ์–ด์ง„ ๋‘ ๋…ธ๋“œ์— ๋Œ€ํ•ด LCA(๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๊ณตํ†ต ์กฐ์ƒ)์„ ๊ตฌํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค. 1๋ฒˆ๊ณผ 2๋ฒˆ์˜ ์ฐจ์ด๋Š” ๋…ธ๋“œ์˜ ์ตœ๋Œ€ ๊ฐฏ์ˆ˜ ๋ฐ ์‹œ๊ฐ„ ์ œํ•œ์˜ ์ฐจ์ด์ด๋‹ค. LCA2๊ฐ€ ํ›จ์”ฌ ๋นก๋นกํ•˜๋‹ค. ํ’€์ด 1. 11437 LCA1๋ฒˆ ํ’€์ด ์—ฐ๊ฒฐ๋œ ๋‘ ๋…ธ๋“œ a,b๊ฐ€ N-1๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ์„œ ์ž…๋ ฅ๋˜๋Š”๋ฐ, a,b์ค‘์— ์–ด๋–ค ๋…ธ๋“œ๊ฐ€ ๋ถ€๋ชจ๋…ธ๋“œ์ธ์ง€๋Š” ์ž…๋ ฅ ๋ฐ›์„ ๋•Œ์—๋Š” ์•Œ ์ˆ˜๊ฐ€ ์—†๋‹ค. ๊ทธ๋ž˜์„œ ์ฒ˜์Œ์—๋Š” ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ ํ˜•ํƒœ๋กœ ์ €์žฅํ–ˆ๋‹ค๊ฐ€, ์ž…๋ ฅ์„ ๋‹ค ๋ฐ›์€ ํ›„์— BFS๋ฅผ ํ†ตํ•ด ๋ฃจํŠธ์ธ 1๋ถ€ํ„ฐ ํƒ€๊ณ  ๋“ค์–ด๊ฐ€์„œ ํŠธ๋ฆฌ๊ตฌ์กฐ๋ฅผ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ๋„๋ก ํ–ˆ๋‹ค. (๊ฐ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ์™€, ๊นŠ์ด ์ €์žฅ) ๊ทธ๋ฆฌ๊ณ  LCA๋ฅผ..
Algorithm 2021. 7. 27. 20:55
์ด์ „ Prev 1 Next ๋‹ค์Œ