[c++] BOJ 1947 :: ์š•์‹ฌ์Ÿ์ด ํŒ๋‹ค
Algorithm ๋ฌธ์ œ/BOJ 2021. 4. 6. 13:11

๋‚œ์ด๋„ : ๊ณจ๋“œ 3 ๊ฑธ๋ฆฐ ์‹œ๊ฐ„ : 20๋ถ„ ๋ฌธ์ œ ์š•์‹ฌ์Ÿ์ด ํŒ๋‹ค ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ ๋ฌธ์ œ n*n์˜ ํฌ๊ธฐ์˜ ๋Œ€๋‚˜๋ฌด ์ˆฒ์ด ์žˆ๋‹ค. ์š•์‹ฌ์Ÿ์ด ํŒ๋‹ค๋Š” ์–ด๋–ค ์ง€์—ญ์—์„œ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋จน๊ธฐ ์‹œ์ž‘ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ๊ณณ์˜ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋‹ค ๋จน์–ด ์น˜์šฐ๋ฉด ์ƒ, ํ•˜, ์ขŒ, ์šฐ ์ค‘ ํ•œ ๊ณณ์œผ๋กœ ์ด๋™์„ ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋˜ ๊ทธ๊ณณ์—์„œ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋จน๋Š”๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๋‹จ ์กฐ๊ฑด์ด ์žˆ๋‹ค. ์ด ํŒ๋‹ค๋Š” ๋งค์šฐ ์š•์‹ฌ์ด ๋งŽ์•„์„œ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋จน๊ณ  ์ž๋ฆฌ๋ฅผ ์˜ฎ๊ธฐ๋ฉด ๊ทธ ์˜ฎ๊ธด ์ง€์—ญ์— ๊ทธ ์ „ ์ง€์—ญ๋ณด๋‹ค ๋Œ€๋‚˜๋ฌด๊ฐ€ ๋งŽ์ด ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๋งŒ์•ฝ์— ๊ทธ๋Ÿฐ ์ง€์ ์ด ์—†์œผ๋ฉด ์ด ํŒ๋‹ค๋Š” ๋ถˆ๋งŒ์„ ๊ฐ€์ง€๊ณ  ๋‹จ์‹ ํˆฌ์Ÿ์„ ํ•˜๋‹ค๊ฐ€ ์ฃฝ๊ฒŒ ๋œ๋‹ค(-_-) ์ด ํŒ๋‹ค์˜ ์‚ฌ์œก์‚ฌ๋Š” ์ด๋Ÿฐ ํŒ๋‹ค๋ฅผ ๋Œ€๋‚˜๋ฌด ์ˆฒ์— ํ’€์–ด ๋†“์•„์•ผ ํ•˜๋Š”๋ฐ, ์–ด๋–ค ์ง€์ ์— ์ฒ˜์Œ์— ํ’€์–ด ๋†“์•„์•ผ ํ•˜๊ณ , ์–ด๋–ค ๊ณณ์œผ๋กœ ์ด๋™์„ ์‹œ์ผœ์•ผ ๋‘˜ ๋‹ค ์†Œ์ค‘ํ•œ ์ƒ๋ช…์ด์ง€๋งŒ ํŒ๋‹ค๊ฐ€ ์ตœ๋Œ€ํ•œ ์˜ค๋ž˜ ..