[백준] 9663 N-Queen

Hyun·2024년 3월 14일

백준 백트래킹

백준

목록 보기

49/81

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력

예제 출력

풀이

dfs-재귀를 이용해 풀이하였다. 그러나 2차원,1차원 배열을 이용한 풀이 모두 python3 에서 시간초과가 발생했고, 1차원 배열을 이용한 풀이는 pypy3 에서는 시간 통과가 되었다.

2차원 배열 사용

처음에는 2차원 배열을 사용하였다. i행일 때, 퀸을 놓을 수 있는 좌표인 경우 해당 좌표에 퀸을 표시하고, i+1 행에 대해 다시 재귀함수를 호출해주었다.

이때 주의할 점은 for 문을 이용해 i행에서 퀸을 놓을 수 있는 자리(열)에 모두 퀸을 놓는 작업을 수행하기 때문에, for 문에서 호출한 재귀함수가, 다시 돌아온 경우, 다른 자리(열)에 퀸을 놓은 다음 다시 i+1 행에 대해 재귀함수를 호출하게 된다.

따라서 기존에 놓았던 퀸을 제거해주어야 다른 열에서 진행되는 재귀 함수에서 이전 행까지 놓인 퀸의 위치를 정확하게 알 수 있다.

n = int(input())
arr = [[0 for _ in range(n)] for _ in range(n)]
cnt = 0

def check(i,j): # [i][j] 좌표에 퀸을 놓을 수 있는지 검사
    # 상단 검사
    r = i-1
    while r>=0:
        if arr[r][j] == 1: return False
        r -=1
    # 좌측 상단 검사
    r, c = i-1,j-1
    while r>=0 and c>=0:
        if arr[r][c] == 1: return False
        r -=1
        c -=1
    # 우측 상단 검사
    r,c = i-1,j+1
    while r>=0 and c <= n-1:
        if arr[r][c] == 1: return False
        r-=1
        c+=1
    return True # 다 통과한 경우

def dfs(i): # i 행에서 다시 퀸 놓을 자리 찾음, 0~i-1행까지 놓은상태
    global cnt
    if i == n:
        cnt+=1
        return

    for j in range(n):
        if check(i, j) is True:
            arr[i][j] = 1 
            dfs(i+1)
            arr[i][j] = 0
    return 

dfs(0)
print(cnt)

1차원 배열 사용

2차원 배열을 이용해 모든 좌표의 상황을 파악하고 있는 게 아니라, 1차원 배열을 이용해 인덱스번째 행에 놓인 퀸의 열의 위치만을 가진다.

이렇게하면 인덱스번째 행에 대한 값이 열 하나만 존재하기 때문에(기존엔 0~n-1 행까지 값 다 관리했음), 값을 갈아끼우면 그 자체로 이전에 있던 열의 위치를 제거하게 된다.

퀸을 놓을 수 있는 자리인지 확인하는 것도 간단하다.

n = int(input())
row = [0 for _ in range(n)]
cnt = 0

def check(i):
    for j in range(i):
        if row[j] == row[i] or i-j == abs(row[j]-row[i]):
            return False
    return True 


def dfs(i): # i행에 대해서 dfs 탐색 수행
    global cnt
    if i == n:
        cnt+=1
        return
    for j in range(n):
        row[i] = j
        if check(i): 
            dfs(i+1)
dfs(0)
print(cnt)