[BOJ] ๐ธ N-Queens / ํ์ด์ฌ
๐ธ N-Queens
๋ฌธ์
N-Queen ๋ฌธ์ ๋ ํฌ๊ธฐ๊ฐ N ร N์ธ ์ฒด์คํ ์์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๋ฌธ์ ์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, ํธ์ ๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (1 โค N < 15)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ ๋์ ํ์ด
def nqueen(sol, n):
global count
if len(sol) == n: # ์ ๋ต ๋ฐฐ์ด(sol)์ ๊ธธ์ด๊ฐ n๊ณผ ๊ฐ์์ง๋ฉด, count ์ฆ๊ฐ
count += 1
return 0
candidate = list(range(n)) # 0๋ถํฐ n-1๊น์ง๋ฅผ ํ๋ณด ๋ฐฐ์ด๋ก ๋ง๋ ๋ค.
for i in range(len(sol)):
if sol[i] in candidate: # ๊ฐ์ ์ด์ ์๋ ์ง ํ์ธ
candidate.remove(sol[i]) # ๊ฐ์ ์ด์ ์๋ค๋ฉด ํ๋ณด์์ ์ ์ธ
distance = len(sol) - i
if sol[i] + distance in candidate: # ๊ฐ์ ๋๊ฐ์ฑ ์(+)์ ์๋ ์ง ํ์ธ
candidate.remove(sol[i] + distance) # ๊ฐ์ ๋๊ฐ์ ์์ ์๋ค๋ฉด ํ๋ณด์์ ์ ์ธ
if sol[i] - distance in candidate: # ๊ฐ์ ๋๊ฐ์ ์(-)์ ์๋ ์ง ํ์ธ
candidate.remove(sol[i] - distance) # ๊ฐ์ ๋๊ฐ์ ์์ ์๋ค๋ฉด ํ๋ณด์์ ์ ์ธ
if candidate != []:
for i in candidate:
sol.append(i) # ํ๋ณด์ ์์๋ฅผ ์ ๋ต ๋ฐฐ์ด์ i+1๋ก ์ถ๊ฐ
nqueen(sol, n) # ์ฌ๊ท์ ์ผ๋ก ๋ค์ ํ๋ ํ์ธ
else:
return 0
count = 0
num = int(input())
for i in range(num): # ์ฒซ ํ์ ๊ฒฝ์ฐ์ ์
nqueen([i], num)
print(count)
N-Queens๋ ๋ฐฑํธ๋ํน ์๊ณ ๋ฆฌ์ฆ์ ์์๋ก ์์ฃผ ์ด์ฉ๋๋ ๋ฌธ์ ์ด๋ค. ๋ฐฑํธ๋ํน ์๊ณ ๋ฆฌ์ฆ์ ๋ ธ๋์ ์ ๋ง์ฑ ์ ๊ฒ ํ, ์ ๋งํ์ง ์์ผ๋ฉด ๊ทธ ๋ ธ๋์ ๋ถ๋ชจ๋ก ๋๋์๊ฐ ํ ๋ค๋ฅธ ์์ ๋ ธ๋๋ฅผ ๊ฒ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ฐ์ , ์ฒซ ํ์ ๊ฒฝ์ฐ์ ์๋ฅผ ์ฐ์ ํ๊ณ nqueen ํจ์์ ๋ฃ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ ํ์ ํ๋ณด๊ตฐ์ ๋ง๋ค์ด ์์ ์ค๋ช ํ ๋ฐฑํธ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ ๋ง์ฑ์ด ์๋ ์์๋ ธ๋์ ์ ๋ง์ฑ์ด ์๋ ์์ ๋ ธ๋๋ฅผ ๊ตฌ๋ถํ์ฌ ํ ํ์ฉ ์ถ๊ฐํ๋ฉด์, ์์ฑ๋ ์ ๋ต ๋ฐฐ์ด์ ๋ง๋ค์ด ๋๊ฐ๋ค.
์ฐธ๊ณ ์๋ฃ
'Algorithm > Problem Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote
๋ค๋ฅธ ๊ธ
-
[ํ๋ก๊ทธ๋๋จธ์ค] ๐พ ์์ถ - [3์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / ํ์ด์ฌ
[ํ๋ก๊ทธ๋๋จธ์ค] ๐พ ์์ถ - [3์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / ํ์ด์ฌ
2019.02.02 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ ์ถ์ ํธ๋ํฝ - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / ํ์ด์ฌ / python / KAKAO BLIND RECRUITMENT
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ ์ถ์ ํธ๋ํฝ - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / ํ์ด์ฌ / python / KAKAO BLIND RECRUITMENT
2019.02.01 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ ์ ํ๋ฒ์ค - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python / KAKAO BLIND RECRUITMENT
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ ์ ํ๋ฒ์ค - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python / KAKAO BLIND RECRUITMENT
2019.02.01 -
[ํ๋ก๊ทธ๋๋จธ์ค] ์ด์ํ ๋ฌธ์ ๋ง๋ค๊ธฐ / ํ์ด์ฌ
[ํ๋ก๊ทธ๋๋จธ์ค] ์ด์ํ ๋ฌธ์ ๋ง๋ค๊ธฐ / ํ์ด์ฌ
2019.01.31
๋น๋ฐ๋๊ธ์ ๋๋ค
์ฌ๊ท ๋์ ์ดํ sol.pop() ์ด ๋น ์ง๊ฒ ๊ฐ์ต๋๋ค. ์ถ๊ฐํด์ฃผ๋๊น ์ ๋ต์ด ๋์ต๋๋ค.
์ ๋ต ์ ์ถ์ ํ์ด์ฌ์ผ๋ก ์ ์ถํ๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋น๋๋ค ํ์ด์ฐธ์ผ๋ก ํ์ธ์ N = 14์ผ ๋ 3๋ถ43์ด๊ฐ ๊ฑธ๋ฆฌ๋ค์
pypy3์ผ๋ก ์ ์ถํ๋๊น ํต๊ณผ๋ฉ๋๋ค.
์ด๊ฑฐ pop() ๋น ์ง๊ฑฐ ๋ง์ฃ ?