๋น์ ์ ์ด๋ค ์์ผ๋ก ์ด ๋ฌธ์ ์ ์ ๊ทผ์ ํ๊ณ , ์ด๋ค ์ฌ๊ณ ์ ๊ณผ์ ์ ๊ฑฐ์ณค์ผ๋ฉฐ, ์ด๋ค ๊ณผ์ ์ผ๋ก ํ๋ก๊ทธ๋๋ฐ์ ํ์ผ๋ฉฐ, ์ด๋ค ๋์์ธ ๊ฒฐ์ ์ ํ์ต๋๊น? ๋ง์ฝ ์คํจํ๋ค๋ฉด ๋น์ ์ด ํ๋ ๊ฒ ํน์ ํ์ง ์์๋ ๊ฒ ์ค ๋ฌด์์ด ์คํจ์ ์ฃผ์์ธ์ด์๋ค๊ณ ๋ถ์์ ํ์ญ๋๊น?
์ด๋ฒ ๊ฒฝํ์ ํตํด ๋ฐฐ์ด ๊ฒ์ ๋ฌด์์
๋๊น? ๋ณ๋ก ์์ต๋๊น? ๊ทธ๋ฌ๋ฉด ๋ค์ ํ๋ฒ ์๊ฐํด ๋ณด์ญ์์ค. ๋จ์ ๊ฒฝํ์ ๋ฃ๊ณ , ๋จ๊ณผ ํ ๋ก ํด ๋ณด์ญ์์ค. ๋ฐฐ์ด ๊ฒ๋ ์๋ ์ผ์ ๋ช ์๊ฐ์ ํฌ์ํ๋ ๊ฒ์ ์๊น์ด ์ผ์
๋๋ค.
์ฒ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋, ์๋ฌด ์ด๋ ค์์ด๋ ์ฅ์ ๋ ์์๋์? ์ง๊ธ ๋ค๋์๋ณผ ๋์ ์์ ์ด ๊ฑฐ์น ๊ณผ์ ์ค์ "๊ฐ์ ๋์์ผ๋ฉด ํ๋ ๋ถ๋ถ"์ด ์๋์? ๋ง์ฝ ์ด ๋ฌธ์ ๋ฅผ ๋ค์ ์ฒ์๋ถํฐ ์๋ก ํ๊ธฐ ์์ํ๋ค๋ฉด ์ญ์ ๋๊ฐ์ ๋ฐฉ์์ผ๋ก ํ๋ก๊ทธ๋๋ฐ์ ํ ๊ฒ ๊ฐ์ต๋๊น(see also EightQueenProblemSecondTry)? ์กฐ๊ธ ๋ ๊น๋ํ๊ณ ์๋ฐํ๊ฒ ํธ๋ ๋ฐฉ๋ฒ๋ ์์๊น์? ์ด๋ป๊ฒ ์ฒ์์ ์ ๊ทผํ๋๋ผ๋ฉด ๋ "๊นจ๋ํ" ์ฝ๋๊ฐ ๋์ฌ ์ ์์์๊น์? ๋น์ทํ ๋ฌธ์ ์ ์ง๋ฉดํ์ ๋ ์ผ๋ฐ์ ์ผ๋ก ์ ์ฉํ ์ ์๋ ์ด๋ค "์ถ์์ ํจ๋ฌ๋ค์" ๊ฐ์ ๊ฒ์ ๋ฐ๊ฒฌํ ์ ์์๊น์? ๊ทธ ์ฝ๋๋ฅผ ๋์ ์ฒ์ ๋ณด๋ ์ฌ๋์ด ์๋ค๊ณ ํ์ ๋ ๋ช ๋ถ๋ง์ ๊ทธ ์ฝ๋๋ฅผ ์ดํด์ํฌ ์ ์๊ฒ ์ต๋๊น? ๋ง์ฝ ๊ทธ ์ฌ๋ ํผ์ ๊ทธ ์ฝ๋๋ฅผ ๋ณธ๋ค๋ฉด ์ฝ๊ฒ ์ดํดํ ์ ์์๊น์? ์ฃผ์์ด ์์ด๋์? ํน์ ์ฝ๋ ๋ด์ ์ค๋ณต๋๋ ์ ๋ณด๋ ์์ต๋๊น? ๋ณธ์ธ์ ์๋๊ฐ ๋ชจ๋ ๋ถ๋ช
ํ ๋๋ฌ๋๊ณ ์์ต๋๊น? --๊น์ฐฝ์ค
๋ฌธ์ ๋ฅผ ๋๋ฆ๋๋ก ํด๊ฒฐํ ์ฌ๋๋ค์ StepwiseRefinement๋ฅผ ๊ผญ ๊ณต๋ถํด ๋ณด์ธ์.
์ด๋ฏธ ์๊ณ ๋ฆฌ์ฆ ์์
์๊ฐ์ ํตํด ์๊ฐํด๋ณธ ๋ฌธ์ ์ด๊ธฐ์ ์ฃผ์ ์์ด ๋ฐฑํธ๋ํน(BackTracking) ๊ธฐ๋ฒ์ ์ ํํด์ ์๋์ฝ๋๋ฅผ ์ข
์ด์ ์์ฑํด๋ณด์๊ณ ๊ทธ๋ฅผ ๋ฐํ์ผ๋ก ๊ตฌํ์ ๋ค์ด๊ฐ์ต๋๋ค.(๊ทธ๋ฅ ํธ๊ธฐ์ฌ์์ ์ง๋ฌธ ํ๋. ์๊ณ ๋ฆฌ์ฆ ์์
์์ ๋ฐฑํธ๋ํน์ ๋ฐฐ์ ๋์? ์ต๊ทผ์๋ ๋๋ถ๋ถ AI์ชฝ์ผ๋ก ๋์ง์ด ๋ด์ ๊ฐ๋ฅด์น๋ ๊ฒ์ด ์ถ์ธ์
๋๋ค๋ง... ๊ต์ฌ๊ฐ ๋ฌด์์ด์๋์? --๊น์ฐฝ์ค Foundations of Algorithms Using C++ Pseudocode, Second Edition ์ด์์ต๋๋ค. 
0763706205 --์ด๋์ค) ๋ฐฑํธ๋ํน์ BruteForce์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ฅํ๊ธฐ์ ์ฉ์ดํด์ ์์ ์ ๊ทธ๋ฆฌ ๋ง์ ์๊ฐ์ด ๊ฑธ๋ฆฌ์ง ์์์ต๋๋ค. ๋ง์ผ EightQueenProblem์ ๋ํ ์ฌ์ ์ง์์ด ์์๋ค๋ฉด ๋๋ฒ์งธ ๊ณผ์ ์์ ๋ฌด์ฒ ๋นํฉํ์๊ฒ ๊ฐ์ต๋๋ค. ์ด๋ฒ ๊ธฐํ์ ์ฝ๋์ ์ ์๋๋ ์ค์ํจ์ ์์ผ ํ์ธํ์ต๋๋ค. --์ด๋์ค
0763706205 --์ด๋์ค) ๋ฐฑํธ๋ํน์ BruteForce์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ฅํ๊ธฐ์ ์ฉ์ดํด์ ์์ ์ ๊ทธ๋ฆฌ ๋ง์ ์๊ฐ์ด ๊ฑธ๋ฆฌ์ง ์์์ต๋๋ค. ๋ง์ผ EightQueenProblem์ ๋ํ ์ฌ์ ์ง์์ด ์์๋ค๋ฉด ๋๋ฒ์งธ ๊ณผ์ ์์ ๋ฌด์ฒ ๋นํฉํ์๊ฒ ๊ฐ์ต๋๋ค. ์ด๋ฒ ๊ธฐํ์ ์ฝ๋์ ์ ์๋๋ ์ค์ํจ์ ์์ผ ํ์ธํ์ต๋๋ค. --์ด๋์ค์ด๋ฌธ์ ๋ ์ฒ์ ์ ํด๋ณธ ๋ฌธ์ ๋ผ ๋จผ์ ์ข
์ด์ ์ฒด์คํ์ ๊ทธ๋ฆฌ๊ณ ์ง์ ๋ฌธ์ ๋ฅผ ํ๋ ค๊ณ ํด๋ณด์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ์๊ฐํด๋ธ๊ฒ์ ์ข
์ด์ ์ ๊ณ (1์ฌ์์ ๊ฐ๋ก,์ธ๋ก,๋๊ฐ์ ๊ฐ์์ค์ ์์ ์๋๋ค. 2,๋จผ์ ์ฒซ๋ฒ์งธ ์ฌ์์ ๋๊ณ ๋๋ฒ์งธ ์ฌ์์ด ๋์ผ ์์น๋ฅผ ๊ฒฐ์ ํ๋ค. 3 ๊ฒ์ฌํ๋ ๋ฐฉ๋ฒ์ ๊ฐ๋ก->์ธ๋ก->๋๊ฐ์ ์์ผ๋ก ํ๋ค. 4 ์ฌ์8๊ฐ๊ฐ ๋ค๋์ด๋ฉด
๋์ธ ์๋ฆฌ๋ฅผ ์๋ ค์ฃผ๊ณ ๋๋๋ค.) ์ด ์ ์ ๊ฒ์ ํ ๋๋ก ์ฝ๋ฉ์ ํ์๊ณ ์ฒ์ ์ฌ์์ 0,0์ ๋์์ต๋๋ค. ์๊ฐํ๋๋ก ์ฝ๋ฉ์ ํ๋ค๊ณ ์๊ฐํ๊ณ ์คํ์ ํ์ ๋ฌดํ๋ฃจํ๋ฅผ ๋์์ต๋๋ค. ์ ์ฒ์ ์ฌ์์ด ์ด๋ ์์น์ ๋์ด๋๊ฐ๋ฐ ๊ฑฐ๊ธฐ์ ๋ง๋ ๋ต์ด ์๋๊ฑฐ๋ผ๊ณ ์๊ฐํ๋๋ฐ ๊ทธ๊ฒ์ด ์๋ชป๋์๋ค๊ณ ์๊ฐํฉ๋๋ค. ์ฒ์๋ถํฐ ์ด ๋ฌธ์ ์ ๋ต์ ์๊ณ ์์๋ค๋ฉด ํ๋ก๊ทธ๋จ์ ์ง๋๋ฐ ์ข๋ ๊ฐ๊ฒฐํ ์ฝ๋๋ฅผ ์งค์์์์ํ ๋ฐ ๋์๊ฐ์ด ๋ค์ด์ ์ฝ๋ฉ์ ๋ฉ์ถ๊ณ ์ข ์ด๋ฅผ ๊บผ๋ด ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์์ํ์ต๋๋ค. ํ์ง๋ง ๋ต์ ๋์ค์ง์์๊ณ ์ ๊ฐํธ๋๋ฐฉ์(์ฌ์์ ๋จผ์ ์๋ฌด์์น์๋ ๋๊ณ ๊ทธ์์น์ ๋ง๊ฒ ๊ฐ๋ก์ธ๋ก๋๊ฐ์ ์ ์๋ ๊ณณ์ ๋๋๋ค)์ ๊ทธ๋ฅ ์ฝ๋ฉ์ ํ์์ต๋๋ค. ์ฒ์ ์ฌ์์ ์์น๋ฅผ 8*8์ ๋์๊ฐ๋ฉด์ ๋๊ณ ๊ฒ์ฌ๋ฅผ ํ์์ต๋๋ค. ๋ฌด์ํ๊ธดํ์ง๋ง ๋ต์ ๋์์ต๋๋ค. ๋๋ฒ์งธ ๊ณผ์ ๋ ์ฒ์ ์ฝ๋ฉํ ๋๋ถํฐ ํ์ ํฌ๊ธฐ์ ์ฌ์์ ์ซ์๋ฅผ defineํด์ 썻๊ธฐ 떄๋ฌธ์ ์ซ์๋ง ๋ฐ๊พธ์ด ์ฃผ์์ต๋๋ค. ํ์ง๋ง ๋ต์ด ๋ง๋์ง ํ์ ์ด ์์ง ์์ต๋๋ค. ๊ทธ์ด์ ๋ ์ด๋ฌธ์ ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ๋ชจ๋ฅด๊ธฐ ๋๋ฌธ์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ c++์ 썻๋๋ฐ ๋ฐฉํ๋์ ์ญ ์๋ฐ๋ก ํ๋ฐํ๋ค๊ฐ c++์ ์ด์ด์ ๊ฐ ๋น์ฃผ์ผํด์ ๋๋ฒ๊น ์ ์ด์ฉํ๋ ค๋ ์๊ฐ์ด์๋๋ฐ ๋ฌด์จ๋ฌธ์ ์ง ๋๋ฒ๊น ์ ํ ์์์ด์ ์ฐธ ๋๊ฐํ์ต๋๋ค. ๋๋ฒ๊น ํ๋ฉด ๊ธ๋ฐฉ์์์๋ ๋ฌธ์ ๋ฅผ ๋์ผ๋ก ์ฐจ๊ทผ์ฐจ๊ทผ 훓์ผ๋ฉด์ ๋ด์ผํ์ต๋๋ค. --์ต๊ด์
๋์ธ ์๋ฆฌ๋ฅผ ์๋ ค์ฃผ๊ณ ๋๋๋ค.) ์ด ์ ์ ๊ฒ์ ํ ๋๋ก ์ฝ๋ฉ์ ํ์๊ณ ์ฒ์ ์ฌ์์ 0,0์ ๋์์ต๋๋ค. ์๊ฐํ๋๋ก ์ฝ๋ฉ์ ํ๋ค๊ณ ์๊ฐํ๊ณ ์คํ์ ํ์ ๋ฌดํ๋ฃจํ๋ฅผ ๋์์ต๋๋ค. ์ ์ฒ์ ์ฌ์์ด ์ด๋ ์์น์ ๋์ด๋๊ฐ๋ฐ ๊ฑฐ๊ธฐ์ ๋ง๋ ๋ต์ด ์๋๊ฑฐ๋ผ๊ณ ์๊ฐํ๋๋ฐ ๊ทธ๊ฒ์ด ์๋ชป๋์๋ค๊ณ ์๊ฐํฉ๋๋ค. ์ฒ์๋ถํฐ ์ด ๋ฌธ์ ์ ๋ต์ ์๊ณ ์์๋ค๋ฉด ํ๋ก๊ทธ๋จ์ ์ง๋๋ฐ ์ข๋ ๊ฐ๊ฒฐํ ์ฝ๋๋ฅผ ์งค์์์์ํ ๋ฐ ๋์๊ฐ์ด ๋ค์ด์ ์ฝ๋ฉ์ ๋ฉ์ถ๊ณ ์ข ์ด๋ฅผ ๊บผ๋ด ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์์ํ์ต๋๋ค. ํ์ง๋ง ๋ต์ ๋์ค์ง์์๊ณ ์ ๊ฐํธ๋๋ฐฉ์(์ฌ์์ ๋จผ์ ์๋ฌด์์น์๋ ๋๊ณ ๊ทธ์์น์ ๋ง๊ฒ ๊ฐ๋ก์ธ๋ก๋๊ฐ์ ์ ์๋ ๊ณณ์ ๋๋๋ค)์ ๊ทธ๋ฅ ์ฝ๋ฉ์ ํ์์ต๋๋ค. ์ฒ์ ์ฌ์์ ์์น๋ฅผ 8*8์ ๋์๊ฐ๋ฉด์ ๋๊ณ ๊ฒ์ฌ๋ฅผ ํ์์ต๋๋ค. ๋ฌด์ํ๊ธดํ์ง๋ง ๋ต์ ๋์์ต๋๋ค. ๋๋ฒ์งธ ๊ณผ์ ๋ ์ฒ์ ์ฝ๋ฉํ ๋๋ถํฐ ํ์ ํฌ๊ธฐ์ ์ฌ์์ ์ซ์๋ฅผ defineํด์ 썻๊ธฐ 떄๋ฌธ์ ์ซ์๋ง ๋ฐ๊พธ์ด ์ฃผ์์ต๋๋ค. ํ์ง๋ง ๋ต์ด ๋ง๋์ง ํ์ ์ด ์์ง ์์ต๋๋ค. ๊ทธ์ด์ ๋ ์ด๋ฌธ์ ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ๋ชจ๋ฅด๊ธฐ ๋๋ฌธ์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ c++์ 썻๋๋ฐ ๋ฐฉํ๋์ ์ญ ์๋ฐ๋ก ํ๋ฐํ๋ค๊ฐ c++์ ์ด์ด์ ๊ฐ ๋น์ฃผ์ผํด์ ๋๋ฒ๊น ์ ์ด์ฉํ๋ ค๋ ์๊ฐ์ด์๋๋ฐ ๋ฌด์จ๋ฌธ์ ์ง ๋๋ฒ๊น ์ ํ ์์์ด์ ์ฐธ ๋๊ฐํ์ต๋๋ค. ๋๋ฒ๊น ํ๋ฉด ๊ธ๋ฐฉ์์์๋ ๋ฌธ์ ๋ฅผ ๋์ผ๋ก ์ฐจ๊ทผ์ฐจ๊ทผ 훓์ผ๋ฉด์ ๋ด์ผํ์ต๋๋ค. --์ต๊ด์
๋๋ฒ์งธ ๋ฌธ์ ์ ๋ต์ด ์์๊ตฐ์.. ์ญ์ ์ ๋ต์ด ํ๋ฆฌ๊ตฐ์ ์คํจ์ ์์ธ์ ์ ๋๋ ์๊ณ ๋ฆฌ์ฆ์ด ์๋ค๋ ๊ฒ์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค BackTracking ์๊ณ ๋ฆฌ์ฆ์ ๋ณด๊ณ ์์ง๋ง ์ด๋ฌธ์ ์ ๋ํ ์ค๋ช
๋ ๋ณด์์ต๋๋ค. ํ์ง๋ง ์๊ณ ๋ฆฌ์ฆ์ ๋ฌด์งํด์ ๊ทธ๋ฐ์ง ์ ๋์ ๋ค์ด์ค์ง ์์ต๋๋ค. ๊ทธ๋๋ ๋ฐค์ ํ๋ฉด์(์๋ฑํ ๋ต์ด๋ค๋) ์ค๋๋ง์ ์ฌ๋ฐ์์ต๋๋ค. ^^-์ต๊ด์
๊ธฐ๋ณธ์ ์ผ๋ก ์ด ๋ฌธ์ ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ค์ค๋ก ๊ณ ์(invent)ํด ๋ด๋ ๊ฒฝํ์ด ์ค์ํฉ๋๋ค. BackTracking ์๊ณ ๋ฆฌ์ฆ์ ์ ํ ๋ชจ๋ฅด๋ ์ฌ๋๋ ์ด ๋ฌธ์ ๋ฅผ ํ ์ ์์ต๋๋ค. ์๋, ์ด๋ป๊ฒ ์ ๊ทผ์ ํด์ผ BackTracking์ ์ ํ ๋ชจ๋ฅด๋ ์ฌ๋๋ ์ด ๋ฌธ์ ๋ฅผ ์ฝ๊ฒ ํ ์ ์์๊น ์ฐ๋ฆฌ๋ ์๊ฐํด ๋ณด์์ผ ํฉ๋๋ค.
์ ๋ ๋ญ ์๋ฌด๊ฒ๋ ์์ด ๋ฌธ์ ๋ง ๋ณด๊ณ ๋ฐ์ด๋ค์์ต๋๋ค. ์ผ๋จ ๋๋ฒ์ ์คํจ (์์ธํ ๋ด์ฉ์ EightQueenProblemDiscussion)์ดํ ์ธ๋ฒ์งธ๋ก ์ก์ ์๊ฐ์ ์ผ๋จ ํ์ค์ ํ๊ฐ๋ง ๋ง์ด ๋ค์ด๊ฐ๋ค๋ ์ ์ด์์ต๋๋ค. ๊ทธ ์ ์ ์ฐฉ์ํ์ฌ. 8*8์ ๋ชจ๋ ์ ์ ๋๊ฒ ๋ง๋ค์์ต๋๋ค. ์ข ๋นํจ์จ์ ์ธ๋ฐ๋ค๊ฐ ์์ฃผ ์๋ง์ธ ์์ค ๋๋ถ์.. ๋ฌธ์ ๋ ํ์์ง๋ง.. ์์ /๋ณด์์ ์์ฒญ๋ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋๊ตฐ์(์ข
๋ฃ์กฐ๊ฑด์ ์ฐพ์์๊ฐ ์์๋ค๋.. ๊ทธ๋์ ์์ ์ 30๋ถ ์ด์ ๊ฑธ๋ ธ์ต๋๋ค.) ํ...... ์ด๋์ ๋ ๋ง์ ์๊ฐ์ ํ๊ฒ ํ ์์ค์์ต๋๋ค. ใ
ก.ใ
ก;; ์ ์ง ๋ ํ์ ํด ์ง ๋๋์.. --์ ํธ
์๋ ๋ง๋ค์ด๋์๊ฒ์ด ์ ์ฒด๊ฐ ํ์๋๋ ๊ฒ์ด์ฌ์ ํน๋ณํ ๊ณ ์น๊ฒ์ ์์์ต๋๋ค. (๋จ, ๋๋ฒ๊น
๋ฌธ์ ๋ก ์์ค์์ ๋ฌธ์ ๋นผ๊ณ ๋..)
BackTracking ์ด์ผ๊ธฐ๊ฐ ๋์ค๋๋ฐ, ๋๊ฐ ์์ ์๊ฐ์ ๋ค์๊ฒ์ด ์์์ง๋ง ๊ทธ๋ฅ ์ฐ์ต์ฅ์ ํ์ ๊ทธ๋ฆฌ๊ณ ์ง์ ๊ถ๋ฆฌํ๊ณ ์. ๊ฒฐ๊ตญ์ ์ ์ฒด ๋ฐฉ๋ฒ์ ๋ํ ๋น๊ต๋ฐฉ๋ฒ์ด ๋์ด์ (8๋จ๊ณ์ ๋ํ Tree) ์ต์ข ๊ตฌํ๋ถ๋ถ์ BackTracking์ ๋ฐฉ๋ฒ์ด ๋์ด๋ฒ๋ฆฌ๊ธด ํ๋ค์. (์ฌ์ ์ง์์ ๋ํด ์ํฅ๋ฐ์์ ์ด์ฉ์ ์๊ฒ ์ฃ . ์์ ์ ํด๋ณด์ง ์์์ด์์. --;) --์์ฒ
BackTracking ์ด์ผ๊ธฐ๊ฐ ๋์ค๋๋ฐ, ๋๊ฐ ์์ ์๊ฐ์ ๋ค์๊ฒ์ด ์์์ง๋ง ๊ทธ๋ฅ ์ฐ์ต์ฅ์ ํ์ ๊ทธ๋ฆฌ๊ณ ์ง์ ๊ถ๋ฆฌํ๊ณ ์. ๊ฒฐ๊ตญ์ ์ ์ฒด ๋ฐฉ๋ฒ์ ๋ํ ๋น๊ต๋ฐฉ๋ฒ์ด ๋์ด์ (8๋จ๊ณ์ ๋ํ Tree) ์ต์ข ๊ตฌํ๋ถ๋ถ์ BackTracking์ ๋ฐฉ๋ฒ์ด ๋์ด๋ฒ๋ฆฌ๊ธด ํ๋ค์. (์ฌ์ ์ง์์ ๋ํด ์ํฅ๋ฐ์์ ์ด์ฉ์ ์๊ฒ ์ฃ . ์์ ์ ํด๋ณด์ง ์์์ด์์. --;) --์์ฒ
ํ..ํํ.. BackTracking์ด.. ๋ญ์ฃ ? ๊ฑฐ๊พธ๋ก.. ์ถ์ ํ๋ค๋ ์ด์ผ๊ธฐ๊ฐ์๋ฐ.. ใ
กใ
กa --์ ํธ
์ ๋ ์ผ๋จ 10*10๋ฐฐ์ด์ ๋ง๋ค์์ต๋๋ค.(๊ฒฝ๊ณ์ ์๊ฐํ๋ฉด ๊ท์ฐฎ์์ง๋ฏ๋ก..) ๊ทธ๋ค์์ 1~8๊น์ง ๋๋คํ ์๋ฅผ ๋๋ฒ ์ฐพ์์ ๋ณด๋์ ์๋ฌด ์์น์๋ค Queen์์๋ฅผ ์ฐ์ด์ค๋๋ค. ๊ทธ๋ฆฌ๊ณ ๊ทธ ์ฃผ๋ณ์ 8๋ฐฉํฅ์ ๋ ๋ค๋ฅธ ์์ Other๋ก ์ค์ ํด์ค๋๋ค. ์ด์ ๋ฃจํ ๋๋ฉด์ ๊ฒน์น์ง ์๊ฒ ๊ณจ๋ผ์ฃผ๋ฉด์ Queen์ผ๋ก ์ค์ ํด์ฃผ๋ค๊ฐ 8๊ฐ๊ฐ ๋๋ฉด ์ข
๋ฃํ๊ฒ.. --์ธ์
์ ๋ ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ๊ฐ ์ค๋ณ๋ก ์์
์ ํด๋ ๋๊ฒ ์ง๋ง, ๋งต์ ํธ์ด ๋ค์ด๊ฐ ์ ์๋ ์๋ฆฌ๋ฅผ ์ ํ๋ ๊ฒ์ ์์ฃผ๋ก ํ์ต๋๋ค.
์ฒ์์๋ ์๋ฆฌ๋ฅผ ์๋ชป์ ํด ์คํจ ํ์๋ ๋ค์ ์๋ฆฌ๋ก ์ฎ๊ฒจ๊ฐ๋ ๋ฐฉ๋ฒ์ ์๋ชป ์๊ฐํด 1์๊ฐ ์ด์ ์๋ชจํ์ต๋๋ค.
๋๋ฒ์งธ ๋ฌธ์ ์์๋ ์ต์ํ์ ์ฒ์์ ์ฐพ์ ์๋ฆฌ์ ๋ํด ๊ฐ์ฅ ๋ณํ๊ฐ ์ ์ ์๋ฆฌ๋ถํฐ(๊ฐ๋ฅํ) ์๊ฐํ๊ฒ ์ค๊ณ๋ฅผ ์กฐ๊ธ ๋ฐ๊ฟจ์ต๋๋ค.
์ฒ์์๋ ์๋ฆฌ๋ฅผ ์๋ชป์ ํด ์คํจ ํ์๋ ๋ค์ ์๋ฆฌ๋ก ์ฎ๊ฒจ๊ฐ๋ ๋ฐฉ๋ฒ์ ์๋ชป ์๊ฐํด 1์๊ฐ ์ด์ ์๋ชจํ์ต๋๋ค.
๋๋ฒ์งธ ๋ฌธ์ ์์๋ ์ต์ํ์ ์ฒ์์ ์ฐพ์ ์๋ฆฌ์ ๋ํด ๊ฐ์ฅ ๋ณํ๊ฐ ์ ์ ์๋ฆฌ๋ถํฐ(๊ฐ๋ฅํ) ์๊ฐํ๊ฒ ์ค๊ณ๋ฅผ ์กฐ๊ธ ๋ฐ๊ฟจ์ต๋๋ค.
์ด์ ์์ ์์ Foundations of Algorithms Using C++ Pseudocode๋ฅผ ๋ดค์ต๋๋ค. ์๊ณ ๋ฆฌ์ฆ ์์
์๊ฐ์ ๋ฐฑํธ๋ํน๊ณผ EightQueenProblem ๋ฌธ์ ๋ฅผ ๊ต์ฌ๋ฅผ ํตํด ๊ณต๋ถํ ์ฌ๋์๊ฒ ์ด ํ๋์ ์๊ธฐ์ ํจ๊ณผ๊ฐ ๊ฑฐ์ ์๊ฒ ๋๊ตฐ์. ๊ทธ๋ด ์ ๋์ผ์ค์ ์ ๋ง ๋ชฐ๋์ต๋๋ค. ๋์ถฉ "์ด๋ฐ ๋ฌธ์ ๊ฐ ์๋ค" ์ ๋๋ก๋ง ์ธ๊ธ๋์ด ์์ ์ฃผ ์์๋๋ฐ... ์ด๋ ๊ต์ฌ์๋ ๊ตฌ์ฒด์ "ํด๋ต"์ด ๋์์์ง ์์, ICPC(ACM์ ์ธ๊ณ ๋ํ์ ํ๋ก๊ทธ๋๋ฐ ๊ฒฝ์ง๋ํ) ๋ฌธ์ ๊ฐ์ ๊ฒ์ผ๋ก ํ ๊ฑธ ๊ทธ๋ฌ๋ ๋ด
๋๋ค. --๊น์ฐฝ์ค
์.. ์ ์ฒ์ ๋ณธ ๋ฌธ์ ์์ต๋๋ค.
(์ํค ์ญ์ ๋จธ๋ฆฌํธ๋๊ณ ์ฒ์์ธ๋ฐ... ์ด๊ฑฐ ์๋นํ ๋งค๋ ฅ์ ์ด๋ค์..^^;;
๋งค๋ฒ ์ํค๋ ๋ธ๋ก๊ทธ๋.. ์ด์ผ๊ธฐ๋ง ๋ค์ด๋ดค์ง ์ค์ ์ฌ์ฉ์ ์ํด๋ดค๋๋ฐ..
๊ทธ๋ฐ๋ฐ ๋์์ ์์ ์ ๋ค์ด๊ฐ๋ฉด ์ด๋ป๊ฒ ์ฒ๋ฆฌ๋๋๊ฑฐ์ง์? cvs์ฒ๋ผ ๋๋?)
(์ํค ์ญ์ ๋จธ๋ฆฌํธ๋๊ณ ์ฒ์์ธ๋ฐ... ์ด๊ฑฐ ์๋นํ ๋งค๋ ฅ์ ์ด๋ค์..^^;;
๋งค๋ฒ ์ํค๋ ๋ธ๋ก๊ทธ๋.. ์ด์ผ๊ธฐ๋ง ๋ค์ด๋ดค์ง ์ค์ ์ฌ์ฉ์ ์ํด๋ดค๋๋ฐ..
๊ทธ๋ฐ๋ฐ ๋์์ ์์ ์ ๋ค์ด๊ฐ๋ฉด ์ด๋ป๊ฒ ์ฒ๋ฆฌ๋๋๊ฑฐ์ง์? cvs์ฒ๋ผ ๋๋?)
ํ๊ต์์ ์๊ณ ๋ฆฌ์ฆ ์๊ฐ์ ๋๋ฌด ๋ง์ด ๋์๊ธฐ ๋๋ฌธ์ธ์ง.. -_-;; ์ฐ๋ฆฌ ํ๊ต์์๋ BackTracking์ด AI์๊ฐ์ ๋ฐฐ์ฐ๋ ๋ถ๋ถ์ด๋ผ์ ๊ทธ๋ฐ์ง..
BackTracking์ ๋ํด ์ฐพ์๋ณด๋ ๊ฒฐ๊ตญ ์ ๊ฐ ํ ๋ฐฉ๋ฒ์ด ๊ทธ ๋ฐฉ๋ฒ์ด๊ตฐ์. ์๊ณ ๋ฆฌ์ฆ์์ฒด๋ ์ข ํ๋ฆฌ์ง๋ง (์ ๋ฆฌ์ปค์๋ธ๋ฅผ ์ด์ฉ...)
๊ฐ๋ ์ ๋์ผํ ๋ฏํฉ๋๋ค.
BackTracking์ ๋ํด ์ฐพ์๋ณด๋ ๊ฒฐ๊ตญ ์ ๊ฐ ํ ๋ฐฉ๋ฒ์ด ๊ทธ ๋ฐฉ๋ฒ์ด๊ตฐ์. ์๊ณ ๋ฆฌ์ฆ์์ฒด๋ ์ข ํ๋ฆฌ์ง๋ง (์ ๋ฆฌ์ปค์๋ธ๋ฅผ ์ด์ฉ...)
๊ฐ๋ ์ ๋์ผํ ๋ฏํฉ๋๋ค.
์ด์จ๋ ์ฐธ ์ข์์ต๋๋ค. ^^;; ์ด๋ฐ ์๋ฆฌ๋ฅผ ๋ง๋ค์ด์ฃผ์ ์ฃผ์ธ๋๊ป ๊ฐ์ฌ๋๋ฆฝ๋๋ค. 
์์ฆ๋ค์ด '๋ณตํํ๋ฉด ์ ๋ง ์ด์ฌํ ๊ณต๋ถํด์ผ๊ฒ ๋ค'๋ ์๊ฐ์ด ์์ฃผ ๋ญ๋๋ค.
ํนํ ์๋ฃ๊ตฌ์กฐ๋ ์๊ณ ๋ฆฌ์ฆ๊ฐ์ ๊ธฐ๋ณธ ๊ณผ๋ชฉ์ ์ํํ ํ๋๊ฒ ๋๋ฌด ํํ๊ฐ ๋๋...T_T
ํนํ ์๋ฃ๊ตฌ์กฐ๋ ์๊ณ ๋ฆฌ์ฆ๊ฐ์ ๊ธฐ๋ณธ ๊ณผ๋ชฉ์ ์ํํ ํ๋๊ฒ ๋๋ฌด ํํ๊ฐ ๋๋...T_T
๋ด๊ฐ ์กฐ๊ธ ์ฑ์ฅํ๋ ๋งํผ ์ธ์์ด ์ ์ ๋์ด์ง๋๊ฒ ๋๊ปด์ง๋๋ค. ์ธ์์ ๋๊ณ ๊ณ ์๋ ๋ง๋ค~~~
by Da_Answer
