[백준/파이썬][Gold IV] N-Queen - 9663

ChatGPT가 그려준 그림

[Gold IV] N-Queen - 9663

문제 링크

성능 요약

메모리: 120284 KB, 시간: 6540 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 3월 2일 09:54:36

문제 설명

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

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

입력

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

출력

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

풀이

경우의 수를 구하는 알고리즘 문제. 

퀸이 움직이는 동선을 체크해보면 직선으로 움직이는 경우의 수, 우하단으로 움직이는 경우의 수, 좌하단으로 움직이는 경우의 수 3가지가 있다. 

# N-Queens 문제를 깊이 우선 탐색(DFS)으로 해결하는 함수
def dfs(n) :
    # 전역 변수를 사용하여 솔루션 개수 추적
    global ans
    
    # N개의 행에 모두 퀸을 배치했다면 유효한 해 발견
    if n == N :
        # 솔루션 개수 증가
        ans += 1
        return

    # 현재 행의 각 열에 퀸을 배치하는 시도
    for j in range(N) :
        # 현재 위치에 퀸을 배치할 수 있는지 확인
        # v1: 열 검사
        # v2: 대각선 검사 (오른쪽 위에서 왼쪽 아래)
        # v3: 대각선 검사 (왼쪽 위에서 오른쪽 아래)
        # 0은 이전 퀸들에 의해 공격받지 않는 위치를 의미
        if v1[j] == v2[n + j] == v3[n - j] == 0 :
            # 현재 위치를 점유된 것으로 표시
            v1[j] = v2[n + j] = v3[n - j] = 1
            
            # 다음 행에 퀸을 배치하기 위해 재귀 호출
            dfs(n + 1)
            
            # 백트래킹: 다른 가능성을 탐색하기 위해 위치 표시 해제
            v1[j] = v2[n + j] = v3[n - j] = 0

# 솔루션 개수 초기화
ans = 0

# 입력으로부터 체스판 크기(N) 읽기
N = int(input())

# 검사 배열 초기화:
# v1: 열 검사 (N개의 열)
# v2: 오른쪽 위에서 왼쪽 아래 대각선 검사 (2N-1개의 대각선)
# v3: 왼쪽 위에서 오른쪽 아래 대각선 검사 (2N-1개의 대각선)
v1 = [0] * N
v2 = [0] * (2 * N)
v3 = [0] * (2 * N)

# 첫 번째 행부터 DFS 시작
dfs(0)

# 유효한 N-Queens 배치 총 개수 출력
print(ans)

 

set() 을 활용한 풀이

# N-Queens 문제를 깊이 우선 탐색(DFS)으로 해결하는 함수
def dfs(n):
    # 전역 변수를 사용하여 솔루션 개수 추적
    global ans

    # N개의 행에 모두 퀸을 배치했다면 유효한 해 발견
    if n == N:
        # 솔루션 개수 증가
        ans += 1
        return

    # 현재 행의 각 열에 퀸을 배치하는 시도
    for j in range(N):
        # 현재 위치에 퀸을 배치할 수 있는지 확인
        # v1: 열 검사
        # v2: 대각선 검사 (오른쪽 위에서 왼쪽 아래)
        # v3: 대각선 검사 (왼쪽 위에서 오른쪽 아래)
        # 0은 이전 퀸들에 의해 공격받지 않는 위치를 의미
        if j in v1 or (n + j) in v2 or (n - j) in v3:
            continue
            # 현재 위치를 점유된 것으로 표시
        v1.add(j)
        v2.add(n + j)
        v3.add(n - j)

        # 다음 행에 퀸을 배치하기 위해 재귀 호출
        dfs(n + 1)

        # 백트래킹: 다른 가능성을 탐색하기 위해 위치 표시 해제
        v1.remove(j)
        v2.remove(n + j)
        v3.remove(n - j)


# 솔루션 개수 초기화
ans = 0

# 입력으로부터 체스판 크기(N) 읽기
N = int(input())

# 검사 배열 초기화:
# v1: 열 검사 (N개의 열)
# v2: 오른쪽 위에서 왼쪽 아래 대각선 검사 (2N-1개의 대각선)
# v3: 왼쪽 위에서 오른쪽 아래 대각선 검사 (2N-1개의 대각선)
v1 = set()
v2 = set()
v3 = set()

# 첫 번째 행부터 DFS 시작
dfs(0)

# 유효한 N-Queens 배치 총 개수 출력
print(ans)