[Python][SWEA] 2806. N-Queen D3

SW Expert Academy

 

---

🗒️파이썬 코드 풀이

def dfs(i):
    global  ans
    if i >= N :
        ans += 1
        return

    for j in range(N):
        if v1[j] == 0 and v2[i-j] == 0 and v3[i+j] == 0 :
            v1[j] = v2[i - j] = v3[i + j] = 1
            dfs(i+1)
            v1[j] = v2[i - j] = v3[i + j] = 0

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    v1,v2,v3 = [[0] * N*2 for _ in range(3)]
    ans = n = 0
    dfs(n)
    print(f"#{tc} {ans}")

 

 

1. N-Queen 문제는 단순화를 시켜야 한다. 

 

ex ) N = 4

- 열 기준으로 단순화  

-> 이 경우에는  4개의 길이를 가진 리스트를 만든다.

 

- 우측 대각 기준으로 단순화

-> 이 경우 대각선 i+j 의 값이 동일한 경우니까 7개의 리스트를 만든다.

 

-  좌측 대각 기준으로 단순화

-> 이 경우 대각선 i-j 의 값이 동일한 경우니까 7개의 리스트를 만든다.

 

2. 딱 원하는 크기만큼의 리스트를 만들어도 되지만, 편의를 위해 더 크게 만들어도 상관없다.

때문에 N*2 크기 만큼의 리스트를 만들어 주었다. 

 

3.  dfs 재귀함수:

- if 함수

가장 먼저 재귀함수의 탈출 루트를 만들어준다. 

그리고 재귀함수의 끝에 도달했을때는 성공 조건이므로 ans +1을 해준다

(재귀함수에서는 보통 조건은 끝에 도달했을때 값을 추가해줘야 한다.)

 

- dfs 내부

N 크기만큼의 for문을 돌려준다. 그리고 v1,v2,v3에서 방문되지 않는 것들로 필터링을 걸어주고,

방문 처리를 하고 재귀함수를 다시 돌려준다. (i-j의 값이 음수가 나올 수 있는데, 파이썬에서는 큰 문제 없다.)

끝에 방문 처리한 것을 초기화하는 것은 필수!!

 

 

📌  문제 코멘트

N-Queen은 대표적인 백트래킹이고, v1,v2,v3 로직만 알면 풀 수 있는 문제이다

근데 한가지 더 중요한 것은 i-j가 음수 나올때, 나는 리스트로 표현하기 어렵다고 생각했다.

하지만  인덱스의 값이 음수인 경우, 거꾸로 가능하기 때문에 큰 문제는 없다.

이 부분을 잘 기억해두자  !! 

---

📚문제

8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다.

퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.
 

이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.

N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇가지가 있을까?

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


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

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


[출력]

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