[c++] BOJ 1027 :: ๊ณ ์ธต ๊ฑด๋ฌผ
Algorithm ๋ฌธ์ œ/BOJ 2021. 8. 31. 20:59

๋ฌธ์ œ ๊ณ ์ธต ๊ฑด๋ฌผ ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ ์„ธ์ค€์‹œ์—๋Š” ๊ณ ์ธต ๋นŒ๋”ฉ์ด ๋งŽ๋‹ค. ์„ธ์ค€์‹œ์˜ ์„œ๋ฏผ ๊น€์ง€๋ฏผ์€ ๊ฐ€์žฅ ๋งŽ์€ ๊ณ ์ธต ๋นŒ๋”ฉ์ด ๋ณด์ด๋Š” ๊ณ ์ธต ๋นŒ๋”ฉ์„ ์ฐพ์œผ๋ ค๊ณ  ํ•œ๋‹ค. ๋นŒ๋”ฉ์€ ์ด N๊ฐœ๊ฐ€ ์žˆ๋Š”๋ฐ, ๋นŒ๋”ฉ์€ ์„ ๋ถ„์œผ๋กœ ๋‚˜ํƒ€๋‚ธ๋‹ค. i๋ฒˆ์งธ ๋นŒ๋”ฉ (1๋ถ€ํ„ฐ ์‹œ์ž‘)์€ (i,0)๋ถ€ํ„ฐ (i,๋†’์ด)์˜ ์„ ๋ถ„์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ณ ์ธต ๋นŒ๋”ฉ A์—์„œ ๋‹ค๋ฅธ ๊ณ ์ธต ๋นŒ๋”ฉ B๊ฐ€ ๋ณผ ์ˆ˜ ์žˆ๋Š” ๋นŒ๋”ฉ์ด ๋˜๋ ค๋ฉด, ๋‘ ์ง€๋ถ•์„ ์ž‡๋Š” ์„ ๋ถ„์ด A์™€ B๋ฅผ ์ œ์™ธํ•œ ๋‹ค๋ฅธ ๊ณ ์ธต ๋นŒ๋”ฉ์„ ์ง€๋‚˜๊ฑฐ๋‚˜ ์ ‘ํ•˜์ง€ ์•Š์•„์•ผ ํ•œ๋‹ค. ๊ฐ€์žฅ ๋งŽ์€ ๊ณ ์ธต ๋นŒ๋”ฉ์ด ๋ณด์ด๋Š” ๋นŒ๋”ฉ์„ ๊ตฌํ•˜๊ณ , ๊ฑฐ๊ธฐ์„œ ๋ณด์ด๋Š” ๋นŒ๋”ฉ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ํ’€์ด ๊ธฐ์šธ๊ธฐ๋ฅผ ๋น„๊ตํ•˜์—ฌ, ๋” ๊ธ‰๊ฒฉํ•œ ๊ธฐ์šธ๊ธฐ๊ฐ€ ๋‚˜์˜ค๋ฉด ๋ณด์ด์ง€ ์•Š๋Š” ๊ฒƒ์œผ๋กœ ํŒ๋‹จ ๊ฐ€์žฅ ๊ธ‰๊ฒฉํ•œ ๊ธฐ์šธ๊ธฐ๋ฅผ ๊ณ„์† ๊ฐฑ์‹  ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ์— ๋Œ€ํ•ด์„œ ๊ฐ๊ฐ ๋ณด์ด๋Š” ๊ฑด๋ฌผ ๊ฐœ์ˆ˜ ๊ณ„์‚ฐ ์˜ฌ๋ ค๋‹ค..