Pypy로 제출했습니다.
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
문제풀이
1.N*N 크기의 체스판이 있다.
단, N x N 크기의 배열을 선언하지않고,
N 크기의 리스트를 선언한다. board = [-1] * N -> 이 리스트는 뭘 의미하냐?
board[i] = 3 이라고 해보자. -> i번째 행에는 3번째 열에 퀸이 존재한다. 를 의미한다.
2.지금 행에서 퀸을 놓을 수 있는 자리를 탐색한다.
for col in range(N): #지금 row는 고정됐다. col을 한 칸씩 움직여가면서 퀸을 놓을 수 있는지 확인할 것이다.
for col in range(N):
if used_col[col]: # 이미 사용한 열이면 skip
continue
board[row] = col # row행 col열에 퀸 배치
if safe(row): # 충돌 없을 때만 다음 행 진행
used_col[col] = True
back_tracking(row + 1)
used_col[col] = False # 백트래킹
우선 현재 board[row] = col을 해서, 퀸을 놓아보자.
그리고 safe(row)를 호출해서, 다른 퀸들과 겹치는지 보면 될 것이다.
만약에 safe함수에서 True를 리턴받으면, board[row] = col은 퀸을 놓을 수 있는 유효한 자리임을 의미한다.
이제 col은 더이상 퀸을 놓을 수 없다. -> used_col[col] = True 로 처리.
def safe(row) -> bool: # row행에 놓은 퀸이 안전한지 확인
for r in range(row):
# board[row] = 현재 row에 놓은 col
# board[r] = r행에 놓인 col
if board[row] == board[r]: # 같은 열
return False
if abs(board[row] - board[r]) == (row - r): # 같은 대각선
return False
return True정답 코드
import sys
def safe(row) -> bool: # row행에 놓은 퀸이 안전한지 확인
for r in range(row):
# board[row] = 현재 row에 놓은 col
# board[r] = r행에 놓인 col
if board[row] == board[r]: # 같은 열
return False
if abs(board[row] - board[r]) == (row - r): # 같은 대각선
return False
return True
def back_tracking(row):
global count, N
# row == N이면 모든 행에 퀸을 성공적으로 놓은 상태
if row == N:
count += 1
return
for col in range(N):
if used_col[col]: # 이미 사용한 열이면 skip
continue
board[row] = col # row행 col열에 퀸 배치
if safe(row): # 충돌 없을 때만 다음 행 진행
used_col[col] = True
back_tracking(row + 1)
used_col[col] = False # 백트래킹
# 충돌이면 자연스럽게 next col
# 입력 처리
N = int(sys.stdin.readline().strip())
board = [-1] * N # board[row] = col
used_col = [False] * N # 열 체크
count = 0
# 실행
back_tracking(0)
print(count)