NQueen (백트래킹)

문제

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

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

 

입력

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

 

출력

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

 

예제 입력1

8

 

예제 출력1

92

 

 

- 풀이 방법

이 문제의 백트래킹 핵심은 퀸을 놓을 때, 열만 생각하면 된다는 것이다. 퀸은 + 방향으로는 절대 같이 놓을 수 없기 때문이다.

(한 행과 한 열에는 같이 놓을 수 없기 때문에) 한 열에만 퀸을 놓는다고 생각하면 하나의 리스트로 표현이 가능하다.

[2, 4, 1, 3]

-> 인덱스 : row

-> 값 : column

위를 그대로 풀이하면, (4x4사이즈의 체스판에 4개의 퀸을 놓을 수 있는 방법)

첫번째 줄에는 2번째 컬럼에

두번째 줄에는 4번째 컬럼에

세번째 줄에는 1번째 컬럼에

네번째 줄에는 3번째 컬럼에 퀸을 놓는다는 의미

 

[3, 1, 4, 2]

위를 그대로 풀이하면,

첫번째 줄에는 3번째 컬럼에

두번째 줄에는 1번째 컬럼에

세번째 줄에는 4번째 컬럼에

네번째 줄에는 2번째 컬럼에 퀸을 놓는다는 의미

 

이걸 그대로 이해해야 한다. (이게 가장 중요! 이해 못하면 다음단계 진행이 안됨)

 

두번째는 이것이다. 현재 놓은 퀸의 개수를 count하고

현재 놓은 퀸의 수의 길이 만큼 for문을 돌려 이전과 현재 놓을 위치의 퀸이 놓을 수 있는 자리인지를 매번 체크하는 방법이다.

그걸 체크하기 위해서는

1. 리스트에서([2, 4, ?, ?]) 현재 3번째 줄을 놓는다고 가정

  -> 리스트를 돌며 2, 4가 ?에 들어갈 수 없다. (같은 열)

2. 리스트에서 첫번째와 대각선에 있는지 체크 (현재 줄) 3 - (이전줄) idx == (1번째 줄 컬럼) 2 - (현재 놓을 컬럼) 이 같으면 대각선에 있는 것이므로 놓을 수 없다.

이런 두 조건을 통해 현재 놓을 수 있는 위치인지를 체크해 놓을 수 있다면 3번째 ?에 놓을 수 있는 1을 놓는 것이다.

 

그렇게 모든 조건을 체크하며 n이 마지막 줄을 돌게 될 때쯤 만들 수 있다면 result에서 1을 더해 결과적으로 모든 노드를 찾아 개수를 출력해주는 것이다.

n=0일 경우 예시만 보여주고 n=0 ~ n=3까지 올라감

 

위 방식 말고도 DFS와 비슷하게 대각선 2개를 파라미터로 두어 푸는 방식이 있는데, 위 방식이 백 트래킹을 다루는 문제 방식이다. 다음번에는 DFS와 비슷하게 푸는 방법으로 풀 예정

 

- 코드

n = int(input())

# 핵심 : 퀸을 놓을 때, 열만 생각하면 된다. 무조건 한 행에 한개만 배치하는 구조이기 때문에

count = 0
li = [0] * n

def check_queen(row, col) :
  for i in range(row) :
    if li[i] == col :
      return False
    elif abs(row-i) == abs(col-li[i]) :
      return False
  return True
  
def queen(row) :
  global count

  if row == n :
    count += 1
    return
  
  for col in range(n) :
    if check_queen(row, col) :
      li[row] = col
      queen(row+1)

queen(0)
print(count)