์ ๋ต์ ์๋ง๊ฒ ๋์ค๋๋ฐ ์๊พธ ์๊ฐ์ด๊ณผ๊ฐ ๋์ค๋ ๋ถ๋ค์ ์ธ์ด๋ฅผ Python3๊ฐ ์๋ Pypy3๋ก ์ค์ ํ๊ณ ์คํํด๋ณด์๊ธฐ ๋ฐ๋๋๋ค
~๋ชฉ์ฐจ~
๋ฌธ์
์ ํ์ ์ธ Backtracking ๋ฌธ์ ์ ๋๋ค!
https://www.acmicpc.net/problem/9663
๋ฌธ์ ํด๊ฒฐ ํฌ์ธํธ
1. row[i] : i๋ฒ์งธ ํ์์ ํธ์ ์ด ๊ฐ์ ๋ํ๋ด๋ 1์ฐจ์ ๋ฐฐ์ด row๋ฅผ ์ฌ์ฉํจ์ผ๋ก ๋ฉ๋ชจ๋ฆฌ ๋ญ๋น ๋ฐฉ์ง
2. promising ํจ์ : ๋๊ฐ์ ์ ์์นํ๊ฑฐ๋ ๊ฐ์ ์ด์ ์์นํ๋ ๊ฒฝ์ฐ๋ ๋์ด์ ํ์ํ์ง ์์์ผํ๋ค :
3. check[] : ์ด๋ฏธ ๋ฐฐ์น๋ ์ด์ ๋ํด ํ์ ์ฒดํฌํ๊ณ ํด์ ํ๋ ๊ณผ์ ์ ํตํด Backtracking ๊ตฌํ
์์ฑ ์ฝ๋
import sys
input = sys.stdin.readline
def promising(i): # iํ์ ๋ฐฐ์นํ ํธ ๋ํด์ ๋ฌธ์ ์๋์ง ํ์ธ
for k in range(i):
if row[i] == row[k] or abs(row[i] - row[k]) == i - k: # ๊ฐ์ ์ด์ด๊ฑฐ๋ ๊ฐ์ ๋๊ฐ์
return False
return True
def backtracking(i):
global result
if i == N: # ๋ชจ๋ ํ์ ๋ฌธ์ ์์ด ํธ์ ๋ฐฐ์นํ์ ๋
result += 1
return
for j in range(N):
if check[j]: # ์ด๋ฏธ ํธ์ด ๋์ธ column
continue
row[i] = j # iํ j์ด์ ํธ ๋์
if promising(i):
check[j] = True # j์ด ํธ ๋ฐฐ์น ์ฒดํฌ
backtracking(i + 1) # ๋ค์ ํ์ ๋ํด ์ํ
check[j] = False # j์ด ํธ ๋ฐฐ์น ํด์
N = int(input())
row = [0] * N # board[n] = m์ nํ m์ด์ ํธ์ ๋์์์ ์๋ฏธํ๋ค
check = [False] * N
result = 0
backtracking(0)
print(result)
REFERENCE
'๐๋ฌธ์ ํ์ด > ๐งฉBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ฐฑ์ค 1753 ์ต๋จ ๊ฒฝ๋ก | ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ (0) | 2023.05.16 |
---|---|
[Python] ๋ฐฑ์ค 1463 1๋ก ๋ง๋ค๊ธฐ | DP (0) | 2023.05.15 |
[Python] ๋ฐฑ์ค 10819 ์ฐจ์ด๋ฅผ ์ต๋๋ก | ์์ด/์กฐํฉ | Permutations/Combinations (0) | 2023.03.02 |
[Python] ๋ฐฑ์ค 2089 -2์ง์ (0) | 2023.03.02 |
[Python] ๋ฐฑ์ค 1107 ๋ฆฌ๋ชจ์ปจ | EOFError | ๋ธ๋ฃจํธํฌ์ค ์๊ณ ๋ฆฌ์ฆ (0) | 2023.03.02 |