# ๋ฌธ์
N-Queen ๋ฌธ์ ๋ ํฌ๊ธฐ๊ฐ N ร N์ธ ์ฒด์คํ ์์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๋ฌธ์ ์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, ํธ์ ๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
# ์
๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (1 โค N < 15)
# ์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ ์ฒด ์ฝ๋
N = int(input())
# row[ํ_idx] == True๋ฉด ํธ์ด ์๋ ํ
row = [False] * N
# ์ด_idx + ํ_idx == True๋ฉด ํธ์ด ์์
right_cross = [False] * (2 * N - 1)
# ์ด_idx - ํ_idx + N-1 == True๋ฉด ํธ์ด ์์
left_cross = [False] * (2 * N - 1)
# ํธ์ ์กฐํฉ ๊ฐ์
count = 0
def recursive(col_idx):
global count
# ์ด ์ธ๋ฑ์ค๊ฐ N์ด๋ฉด ํธ์ ๋ชจ๋ ๋์ ๊ฑฐ๋๊น count++ ํด์ฃผ๊ณ ๋ฆฌํด
if col_idx == N:
count += 1
return
for row_idx in range(N):
# row_idx ํ์ ํธ์ด ์๊ณ
if (not row[row_idx]
# ์ผ์ชฝ ๋๊ฐ์ ์๋ ํธ์ด ์๊ณ
and not left_cross[N-1 + col_idx - row_idx]
# ์ค๋ฅธ์ชฝ ๋๊ฐ์ ์๋ ํธ์ด ์์ผ๋ฉด
and not right_cross[col_idx + row_idx]):
# row_idx ํ์ ํธ์ ๋๋๋ค.
row[row_idx] = True
left_cross[N-1 + col_idx - row_idx] = True
right_cross[col_idx + row_idx] = True
# ๋ค์ ์ด์ ๋์ ํธ ์ฐพ์ผ๋ฌ ใฑใฑ
recursive(col_idx + 1)
# ๋ค์ ๋ฐ๋ณต์์๋ ์ด ํ์ ๋๋ ๊ฒฝ์ฐ๊ฐ ์๋๋๊น False๋ก ๋ฐ๊ฟ๋๋ค.
row[row_idx] = False
left_cross[N-1 + col_idx - row_idx] = False
right_cross[col_idx + row_idx] = False
recursive(0)
print(count)
ํธ์ ๋ชจ๋ ํ, ์ด, ์์ชฝ ๋๊ฐ์ ์์ ํ๋ก ์์นํด์ผ ํ๋ค.
(์ค๋์ฟ ๋ ๋น์ท?!๐)
์ธ์๋ก ์ด์ index๋ฅผ 0๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฐ๊ณ , ๋ช๋ฒ์งธ ํ index์ ๋ค์ด๊ฐ ์ ์๋์ง ์ฐพ๋ ํจ์๋ฅผ ๋ง๋ ๋ค.
๋ฐ๋ณต๋ฌธ์ ํตํด 0๋ถํฐ N-1๊น์ง ํ ์ค์์
1) ํธ์ด ๋์ด์ง ์์ ํ์ธ์ง
2) ์ค๋ฅธ์ชฝ ์ ๋๊ฐ์ ๋ฐฉํฅ์ผ๋ก ํธ์ด ๋์ด์ง ์์๋์ง
3) ์ผ์ชฝ ์ ๋๊ฐ์ ๋ฐฉํฅ์ผ๋ก ํธ์ด ๋์ด์ง ์์๋์ง
์ ์ธ๊ฐ์ง๋ฅผ ํ์ธํด์ ํธ์ด ๋์ด์ง ์์ ๊ฒฝ์ฐ์ ํธ์ ๋ฐฐ์นํ๋ค.
๊ฐ ๋ฐฐ์ด์์
๊ฐ์ด True
์ด๋ฉด ํธ์ด ์ด๋ฏธ ์๋ ๊ฒ์ด๊ณ ,
False
์ธ ๊ฒฝ์ฐ์๋ ํธ์ด ์์ด์ ๋ฐฐ์นํ ์ ์๋ ๊ฒ์ด๋ค.
row = [False] * N
row[ํ_idx] == True
๋ฉด ํธ์ด ์์
๋ฐฐ์ด์ ๊ธธ์ด๋ N
right_cross = [False] * (2 * N - 1)
right_cross[์ด_idx + ํ_idx] == True
๋ฉด ํธ์ด ์์
๋ฐฐ์ด์ ๊ธธ์ด๋ 2N - 1
์ค๋ฅธ์ชฝ ์๋ฅผ ํฅํ๋ ๋๊ฐ์ ๋ฐฐ์ด ์ธ๋ฑ์ค ์ ํ๊ธฐ
๐๐ป ์ด index์ ํ index๋ฅผ ๋ํ ๊ฐ์ผ๋ก ์ ํ๋ค.
left_cross = [False] * (2 * N - 1)
left_cross[์ด_idx - ํ_idx + N-1] == True
๋ฉด ํธ์ด ์์
๋ฐฐ์ด์ ๊ธธ์ด๋ 2N - 1
์ผ์ชฝ ์๋ฅผ ํฅํ๋ ๋๊ฐ์ ๋ฐฐ์ด ์ธ๋ฑ์ค ์ ํ๊ธฐ
๐๐ป ์ด Index์์ ํ index๋ฅผ ๋นผ๊ณ , N-1์ ๋ํ ๊ฐ์ผ๋ก ์ ํ๋ค.
def recursive(col_idx):
global count
# ์ด ์ธ๋ฑ์ค๊ฐ N์ด๋ฉด ํธ์ ๋ชจ๋ ๋์ ๊ฑฐ๋๊น count++ ํด์ฃผ๊ณ ๋ฆฌํด
if col_idx == N:
count += 1
return
ํจ์์ ์ธ์๋ก ์ด index๋ฅผ ๋ณด๋ด์ค ๊ฑฐ๋๊น,
๋ฐ์ ์ธ์์ ๊ฐ์ด N๊ณผ ๊ฐ์ผ๋ฉด ๋ชจ๋ ๊ณ ๋ฅธ ๊ฒ์ด๋ค.
๋ชจ๋ ๊ณจ๋์ผ๋ฉด, ๋ฌธ์ ์์ ์ํค๋ ๋๋ก ๊ฒฐ๊ณผ๋ก ์ถ๋ ฅํ ๊ฐ์ count
์ +1์ ํด์ฃผ๊ณ , ํจ์๋ฅผ ์ข
๋ฃํ๋ค.
for row_idx in range(N):
# row_idx ํ์ ํธ์ด ์๊ณ
if (not row[row_idx]
# ์ผ์ชฝ ๋๊ฐ์ ์๋ ํธ์ด ์๊ณ
and not left_cross[N-1 + col_idx - row_idx]
# ์ค๋ฅธ์ชฝ ๋๊ฐ์ ์๋ ํธ์ด ์์ผ๋ฉด
and not right_cross[col_idx + row_idx]):
๋ฐ๋ณต๋ฌธ์ ํตํด ๋์ค๋ 0๋ถํฐ N-1๊น์ง์ ๊ฐ์ด ํ (row_idx
)์ด ๋๋ค.
ํจ์์ ์ธ์๋ก ๋ฐ๋ ๊ฐ(col_idx
)๊ฐ ์ด์ด๋ค.
์ด๋ฆ ๊ทธ๋๋ก..๐
์ด์ ์ค๋ณต์ ์ฒดํฌํ ํ์๊ฐ ์๋ค! ์ด ์ด์๋ ์ง๊ธ ํธ์ ๋ฐฐ์นํ๋ ์๊ฐ์ด ์ฒ์ ๋์์ง๋ ๊ฒ์ด๋ค.
ํด๋น row_idx
ํ์ ํธ์ด ๋ฐฐ์น๋์ด์์ง ์์์ง ํ์ธํ๋ค.
์ผ์ชฝ ๋๊ฐ์ ๊ณผ ์ค๋ฅธ์ชฝ ๋๊ฐ์ ์๋ ๋ง์ฐฌ๊ฐ์ง๋ก
ํธ์ด ๋ฐฐ์น๋์ด์์ง ์์์ง ํ์ธํ๋ค.
์ธ ๋ฐฐ์ด์์ ์ฐพ์ ๊ฐ์ด ๋ชจ๋ False
๋ผ๋ฉด, ํธ์ ๋์ ์๋ฆฌ๋ฅผ ์ฐพ์ ๊ฒ์ด๋ค!! ๐ฅ
# col_idx ์ด & row_idx ํ์ ํธ์ ๋๋๋ค.
row[row_idx] = True
left_cross[N-1 + col_idx - row_idx] = True
right_cross[col_idx + row_idx] = True
๋ค์ ์ด์๋ ์ด ์์น์ ํธ์ ๋์ผ๋ฉด ์๋๋๊น True๋ก ํ์๋ฅผ ํด๋๋ค.
์ด๋ฌ๋ฉด ๋ค์ ์ด์์ ํธ ์์น๋ฅผ ์ฐพ์ ๋๋ 3๋จ๊ณ์ ์กฐ๊ฑด๋ฌธ์ ์ํด ์ด ์์น์ ํธ์ ๋์ง ์๊ฒ ์ง!!
# ๋ค์ ์ด์ ๋์ ํธ ์ฐพ์ผ๋ฌ ใฑใฑ
recursive(col_idx + 1)
col_idx
๊ฐ N
๊ณผ ๊ฐ์์ง ๋๊น์ง 3~5๋จ๊ณ๋ฅผ ๋ฐ๋ณตํ๋ค.
col_idx
๊ฐ N
๊ณผ ๊ฐ์์ง๋ฉด, 2๋จ๊ณ์ if๋ฌธ์ผ๋ก ๋น ์ง๊ณ ํจ์๊ฐ ์ข
๋ฃ๋๋ค.
# ๋ค์ ๋ฐ๋ณต์์๋ ์ด ํ์ ๋๋ ๊ฒฝ์ฐ๊ฐ ์๋๋๊น False๋ก ๋ฐ๊ฟ๋๋ค.
row[row_idx] = False
left_cross[N-1 + col_idx - row_idx] = False
right_cross[col_idx + row_idx] = False
์ฌ๊ธฐ์ ์๋ฏธํ๋ ๋ค์ ๋ฐ๋ณต์ recursive ํจ์์ ๋ฐ๋ณต์ด ์๋,
for๋ฌธ์ ๋ฐ๋ณต์ ์๋ฏธํ๋ค.
์ฆ, ์ง๊ธ col_idx์ ๋ค๋ฅธ ํ์ ํธ์ ๋ฐฐ์นํ๋ ๊ฒฝ์ฐ๋ฅผ ์ฐพ๊ธฐ ์ํด for๋ฌธ์ด ๋์๊ฐ๋ ๊ฑฐ๋๊น
์ง๊ธ ๋์ ํ์ ์์น๋ ์์ ์ค์ผ ํ๋ค.
๊ทธ๋ฌ๋๊น ์์๋ณต๊ท ใฑใฑ ๐๐ป True๋ก ๋ฐ๊พผ ๊ฐ์ ๋ค์ False ๊ฐ์ผ๋ก ๋ฐ๊ฟ์ค๋ค.