[Python] 백준 9663번, N-Queen

문제링크 : https://www.acmicpc.net/problem/9663

1. 문제

2. 풀이

백트래킹을 사용하여 풀 수 있는 문제이다.

• 퀸은 한 방향으로 동서남북, 대각선을 자유자제로 이동할 수 있다. 따라서
  ✔️ 퀸이 서로 공격을 할 수 없는 자리에 n개를 놓는 경우의 수를 세어야한다.

• 보드판의 각 위치를 [x, y]로 생각해보면, 같은 행(즉, 같은 y)에 위치한 퀸은 서로 싸우게 된다.
  - 따라서, y 끼리 같은 것을 지운다.

• 또한, 대각선 방향의 위치를 판별할 때, 1차 함수의 기울기 공식을 생각하면 된다.

  • 함수의 기울기 공식 : (y1 - y2)/(x1 - x2)
  • 이 공식의 값이 1 이면 대각선으로 이어지게 된다.
  • 따라서 이를 이용하여, 행1 - 행2 = 열1 - 열2 을 조건문으로 두어 퀸을 두기 올바른 자리인지 판별한다.

• dfs로 탐색을 하되, 조건문으로 가지치기를 하여 처음으로 다시 돌아가게 만들고 다른 경로를 탐색하게 해야한다.

3. 코드

import sys
input = sys.stdin.readline

n = int(input())

row = [0] * n	# 보드판의 열을 표현할 리스트
cnt = 0	# 가능한 경우의 수

def find(x):	# 경우의 수 판별
    for i in range(x):
    # 같은 행 이거나 대각선(행-행 == 열-열, 기울기공식) 위치인지 판별
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:	
            return False
    return True

def dfs(x):
    global cnt
    # 말을 전부 올바른 곳에 두었다면 횟수
    if x == n:
        cnt += 1

    else:
    # [0, 0] 부터 말을 두기 시작
        for i in range(n):
            row[x] = i
            if find(x):	# 가지치기 - 올바른 경우가 아닐 때, 다시 돌아가 다시 탐색
                dfs(x + 1)

dfs(0)
print(cnt)