N-Queen Python(SW Expert Academy)

난이도 : D3

문제번호 : 2806

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다. N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까? N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 N(1 ≤ N ≤ 10)이 주어진다.

출력

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예시

입력	출력
2 1 2	#1 1 #2 0

---

2. 문제풀이

퀸은 가로 세로 대각선으로 이동이 가능하다. 따라서 모두 공격이 불가능한 경우를 만들기 위해서는 각각의 퀸들이 가로 세로 대각선상에 놓여있으면 안된다. 그렇다면 나는 행, 열, 대각선을 체크해야 한다.   dfs를 이용하여 문제를 푸는데 index로 행을 넘겨준다. index는 계속 늘어나므로 겹치는 일이 없다.   반복문을 이용하여 열을 체크한다. 해당 열을 사용한 적이 없다면 대각선을 체크하고 대각선상에 없다면 해당 열을 사용했다고 체크하고 넘어간다.   대각선을 계산하기 위해 x축의 차이와 y축의 차이가 같은지 보면된다. 행이 마지막까지 도달했다면 count를 증가시킨다.

---

3. 소스코드

#D3 2806 N-Queen
 
#대각선 체크 함수
def possible(idx, c):
    for i in range(idx):
        #행과 열의 차이가 같다면
        if idx - i == abs(c - map_list[i]): return True
    return False
    
def dfs(idx):
    if idx == N:
        global answer
        answer += 1
        return
    for i in range(N):
        #이미 사용한 열이라면 넘어감
        if visit[i] : continue
        #대각선이 겹친다면 넘어감
        if possible(idx, i) : continue
        visit[i] = 1
        map_list[idx] = i
        dfs(idx + 1)
        visit[i] = 0
 
for t in range(1, int(input()) + 1):
    N = int(input())
    map_list = [0 for _ in range(N)]
    visit = [0 for _ in range(N)]
    answer = 0
    dfs(0)
    print('#{} {}'.format(t, answer))