๐Ÿ‘‰Backtracking

๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ „๋ถ€ ๊ณ ๋ คํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜. ์ผ์ข…์˜ ํŠธ๋ฆฌ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜. ๊ตฌ์กฐ์ ์œผ๋กœ ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰(DFS)์„ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•œ๋‹ค. ์ฆ‰, DFS์˜ ๊ตฌ์กฐ๋ฅผ ์ ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์— ์ ์šฉ๋  ์ˆ˜ ์žˆ๋‹ค.

์–ด๋–ค ๋…ธ๋“œ์˜ ์œ ๋ง์„ฑ์„ ์ ๊ฒ€ํ•˜๊ณ  ์œ ๋งํ•˜์ง€ ์•Š์œผ๋ฉด ๊ทธ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ๋Œ์•„๊ฐ„ ํ›„ ๋‹ค๋ฅธ ์ž์†์˜ ๋…ธ๋“œ๋ฅผ ๊ฒ€์ƒ‰ํ•˜๋Š” ๊ฒƒ. ์ฆ‰, ์Šคํƒ์— ์ž์‹๋…ธ๋“œ๋ฅผ ๋„ฃ๊ธฐ ์ „์— ์œ ๋งํ•œ์ง€ ํ™•์ธํ•˜๊ณ  ์Šคํƒ์— ๋„ฃ์Œ

๋ฐฑํŠธ๋ž™ํ‚น์˜ ๊ฒฝ์šฐ ๊ฐ€์ง€์น˜๊ธฐ๊ฐ€ ์ผ์–ด๋‚˜๋ฏ€๋กœ ์›์‹œ์ ์ธ ๋ฐฉ๋ฒ•์œผ๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํ™•์ธํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•„๋‹ˆ๋‹ค.

๐Ÿ—ฟ N-Queens

N-queens.PNG

N * N ๋ฐฐ์—ด์ผ ๋•Œ ์ฒด์Šค(ํ€ธ) ๋ง์ด ๊ฐ€๋กœx์„ธ๋กœx๋Œ€๊ฐ์„ ์— ๊ฐ™์ด ๋†“์ผ ์ˆ˜ ์—†๊ฒŒ ์ž‘์„ฑํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

๋ฌธ์ œ ํ’€์ด์—์„œ Help Function์˜ ์˜๋ฏธ์™€ ์‚ฌ์šฉ์— ๋Œ€ํ•ด ๋ถ„์„์„ ํ•˜๊ณ , N-Queens ๊ฐ row / col / Digonal ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•œ๋‹ค.

๐Ÿ‘‰์ž‘์„ฑํ•จ์— ์žˆ์–ด์„œ ์ •ํ™•ํ•˜๊ฒŒ ๋ถ„์„๋ถ€ํ„ฐ ํ•˜๊ณ  ์ง„ํ–‰ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ฐ ํ•จ์ˆ˜๋“ค์˜ ์˜๋ฏธ๋„ ์ •ํ™•ํ•˜๊ฒŒ ํŒŒ์•…ํ•ด์•ผํ•œ๋‹ค.