[๋ฐฑ์ค/pypy3] 9663๋ฒ : N-Queen
๋ฌธ์
N-Queen ๋ฌธ์ ๋ ํฌ๊ธฐ๊ฐ N × N์ธ ์ฒด์คํ ์์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๋ฌธ์ ์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, ํธ์ ๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N < 15)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ ๋ต
N = int(input())
count = 0
# row : ํ / right : ์ฐ์ํฅ ๋๊ฐ์ / left : ์ข์ํฅ ๋๊ฐ์
row, right, left = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)
def solve(j):
global count
# N๊ฐ์ ํธ์ ๋ค ๋์์ ๋
if j == N:
count += 1
return
for i in range(N):
# ๋ชจ๋ ๋ฐฉํฅ์ด False์ผ ๋ = ํธ์ ๋์ ์ ์์ ๋
if not (row[i] or right[j + i] or left[N - 1 + j - i]):
row[i] = right[j+i] = left[N-1+j-i] = True
solve(j+1)
row[i] = right[j+i] = left[N-1+j-i] = False
solve(0)
print(count)
์ด ๋ฌธ์ ๋ ํ์ด์ฌ์ ํตํด ํ ๊ฒฝ์ฐ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ pypy3๋ฅผ ์ฌ์ฉํด์ผ ํ ์ ์๋ค.
# row : ํ / right : ์ฐ์ํฅ ๋๊ฐ์ / left : ์ข์ํฅ ๋๊ฐ์
row, right, left = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)
์ขํ์ ๋ ์ธ๋ฑ์ค์ ํฉ ๋๋ ์ฐจ๊ฐ ๋ค๋ฅธ ์ขํ์ ํฉ ๋๋ ์ฐจ๊ฐ ๊ฐ๋ค๋ฉด ๊ฐ์ ๋๊ฐ์ ์์ ์กด์ฌํจ์ ์ด์ฉํ๋ค.
์๋ฅผ ๋ค์ด (0,2), (1,1), (2,0)์ ๋ ์ธ๋ฑ์ค์ ํฉ์ 2๋ก ๋ชจ๋ ๊ฐ์ผ๋ฏ๋ก ๊ฐ์ ์ฐ์ํฅ ๋๊ฐ์ ์์ ์์นํ๋ค.
๋๊ฐ์ ์ ๋ํ๋ด๋ right์ left๋ ๋ ์ธ๋ฑ์ค์ ํฉ๊ณผ ์ฐจ๋ก ์ด๋ฃจ์ด์ง๋ฏ๋ก 2*N-1๊ฐ์ ์ธ๋ฑ์ค๊ฐ ํ์ํ๋ค.
def solve(j):
global count
# N๊ฐ์ ํธ์ ๋ค ๋์์ ๋
if j == N:
count += 1
return
solve ํจ์๋ฅผ ๋ง๋ค๊ณ ํ์ ์๋ฏธํ j๋ฅผ ์ธ์๋ก ์ฌ์ฉํ์ฌ ๋ชจ๋ ํ์ ํธ์ ๋์ ๊ฒ์ด๋ค.
j๊ฐ N๊ณผ ๊ฐ๋ค๋ฉด ๋์์ผ ํ๋ ๊ฐ์์ ํธ์ ๊ฐ ํ๋ง๋ค ๋ค ๋์๋ค๋ ๋ป์ด๊ธฐ ๋๋ฌธ์
ํธ์ ๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์๋ฏธํ๋ count์ 1์ ๋ํด์ฃผ๊ณ return ํ๋ค.
for i in range(N):
# ๋ชจ๋ ๋ฐฉํฅ์ด False์ผ ๋ = ํธ์ ๋์ ์ ์์ ๋
if not (row[i] or right[j + i] or left[N - 1 + j - i]):
row[i] = right[j+i] = left[N-1+j-i] = True
solve(j+1)
row[i] = right[j+i] = left[N-1+j-i] = False
์ด์ ๋งจ ์ ํ๋ถํฐ ์์ํ์ฌ ์์๋๋ก ๋ด๋ ค๊ฐ๋ฉด์ ๋ชจ๋ ์ด์ ํธ์ ๋๋๋ค.
๋ชจ๋ ์ด i์ ๋ํ์ฌ ๋ค์ ๋ฐ๋ณต๋ฌธ์ ์คํํ๋ค.
ํด๋น ์ด์ ํ, ๋๊ฐ์ ์ด ๋ชจ๋ False๋ผ๋ฉด ํธ์ ๋์ ์ ์๋ค๋ ๋ป์ด๋ฏ๋ก
ํด๋น ์ด์ ํ, ๋๊ฐ์ ์ True๋ก ๋ฐ๊ฟ์ฃผ๊ณ ๋ค์ ํ์ธ solve(j+1)์ ํธ์ถํ๋ค.
๋ค์ ๊ฒฝ์ฐ์ ์๋ฅผ ์ธ๊ธฐ ์ํด ํ๊ณผ ๋๊ฐ์ ์ ์๋ฏธํ๋ row, right, left๋ฅผ ๋ค์ Flase๋ก ์ด๊ธฐํํ๋ค.
์๋ ์ฃผ์์ ์ค๋ช ์ ์ฐธ๊ณ ํ์๋ค.
'๐์๊ณ ๋ฆฌ์ฆ > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค/python] 2579๋ฒ : ๊ณ๋จ ์ค๋ฅด๊ธฐ (0) | 2021.04.13 |
---|---|
[๋ฐฑ์ค/python] 11054๋ฒ : ๊ฐ์ฅ ๊ธด ๋ฐ์ดํ ๋ ๋ถ๋ถ ์์ด (0) | 2021.04.13 |
[๋ฐฑ์ค/python] 15650๋ฒ : N๊ณผ M (0) | 2021.04.11 |
[๋ฐฑ์ค/python] 2667๋ฒ : ๋จ์ง๋ฒํธ ๋ถ์ด๊ธฐ (0) | 2021.04.07 |
[๋ฐฑ์ค/python] 2630๋ฒ : ์์ข ์ด ๋ง๋ค๊ธฐ (0) | 2021.04.06 |