[Python] 백준 9663번_N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

• N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
• N이 주어졌을 때, 퀸을 놓는 방법의 수 구하기

• 입력
  • 첫째 줄에 N이 주어짐 (1 ≤ N < 15)
• 출력
  • 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력
• 시간 제한: 10초
• 메모리 제한: 128 MB

 

"""
입출력 예시)

8 -> 92
"""

 

 

## 의사코드 ##

# 백트래킹 -> dfs
# 체스에서의 퀸: 수직, 수평, 대각선으로 이동 가능

# Pruning (가지치기)
# 한 행에는 하나의 퀸만 배치 가능
# 맨 위의 행부터 dfs로 탐색

# Promising (조건 체크)
# 수직 체크
#   -> 열의 값이 같은 경우
# 대각선 체크
#   -> abs(퀸의 열 - 현재 열) == 1
# -> 둘 다 만족하지 않는 경우만 True

 

 

 

첫 번째 시도

 

n = int(input())
row = [] * n # N x N 체스판
result = 0 # 퀸을 배치하는 경우의 수

# Promising (조건 체크)
def check(x): 
    # x번째 행의 이전 행에 놓은 퀸에 대해 검증
    for i in range(x):
        # 수직 체크 혹은 대각선 체크 중 하나라도 만족하는 경우
        if row[x] == row[i] or abs(row[x] - row[i]) == 1:
            return False # False
    return True # 둘 다 만족하지 않는 경우 

# Pruning (가지치기)
def dfs(x):
    global result 
    if x == n:
        result += 1
    else:
        # x번째 행의 각 열에 대해 검증
        for i in range(n):
            row[x] = i # row[x] => 열 
            # 해당 위치에 퀸을 배치할 수 있는 경우
            if check(x):
                # 다음 행으로 넘어가기 
                dfs(x+1) 

dfs(0)
print(result)

-> 런타임 에러 (PyPy3로 제출)

-> IndexError 발생 (row = [] * n 때문)

 

 

통과한 코드

 

n = int(input())
row = [0] * n # N x N 체스판
result = 0 # 퀸을 배치하는 경우의 수

# Promising (조건 체크)
def check(x): 
    # x번째 행의 이전 행에 놓은 퀸에 대해 검증
    for i in range(x):
        # 수직 체크 혹은 대각선 체크 중 하나라도 만족하는 경우
        if row[x] == row[i] or abs(row[x] - row[i]) == x-i:
            return False # False
    return True # 둘 다 만족하지 않는 경우 

# Pruning (가지치기)
def dfs(x):
    global result 
    if x == n:
        result += 1
        return 
    else:
        # x번째 행의 각 열에 대해 검증
        for i in range(n):
            row[x] = i # row[x] => 열 
            # 해당 위치에 퀸을 배치할 수 있는 경우
            if check(x):
                # 다음 행으로 넘어가기 
                dfs(x+1) 

dfs(0)
print(result)

-> 대각선 체크 조건을 abs(row[x] - row[i]) == 1 에서 'abs(row[x] - row[i]) == x-i' 로 수정,

      'row = [0] * n' 으로 수정

 

-> PyPy3로 제출해야 통과

 

 

 

cf) 이전에 작성했던 코드

 

https://monzheld.tistory.com/63

[Python] 백준 9663번_N-Queen