BOJ 백준 9663번 N-Queen | SW Expert Academy 2806번 N-Queen | Python
📌 SW Expert Academy 2806번 문제 바로가기
🔎 문제 설명
💛 백준 Gold4 / SW Expert D2
- 난이도 ★★★☆
- 그래프탐색 DFS
백준 그리고 SW Expert Academy 사이트에 거의 완전히 같은 문제라 같이 가져왔다.
보드가 나와있어서 단순히 2차원 배열로 해결할 수 있지만, 상하좌우와 대각선에서 겹치지 않는지만 확인하면 된다. 그래서 단순히 1차원 배열 인덱스를 열 번호, 배열값을 행 번호로 저장하면 1차원으로도 충분히 구현이 가능하다.
📌 문제 풀이 큰 틀
attack함수를 통해 상하좌우, 대각선에서 겹치는지 확인- 겹치지 않는다면 DFS로 계속 탐색 진행
- 1차원 배열 인덱스를 열 번호, 배열값을 행 번호로 저장
💻 내 코드
SW Expert Academy 문제 기준 코드이다. 아마 백준에서는 T에 관한 부분만 제거를 해주면 쉽게 통과할 수 있을 것이다.
T = int(input())
def attack(node):
for i in range(node):
if board[i] == board[node] or abs(board[i]-board[node]) == abs(i-node):
return True
return False
def dfs(start):
global cnt
if start == N:
cnt += 1
return
for i in range(N):
board[start] = i
if not attack(start):
dfs(start+1)
for t in range(T):
cnt = 0
N = int(input())
board = [-1 for _ in range(N)]
dfs(0)
print(f'#{t+1} {cnt}')
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).