[Python] 백준 9963(N-Queen)

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

백트래킹의 대표 유형급인 문제이다.

- 퀸의 위치마다 서로 공격할 수 없는 퀸의 위치가 달라짐 --> 가지치기

- 모든 퀸의 배치를 끝냈다면 돌아가기 -->  백트래킹

 

✅ 풀이

n = int(input())
answer = 0
col = [False] * n    # 각 열에 퀸이 있는지 여부를 판단하기 위한 배열
diagonal1 = [False] * (n * 2)  # 우상 -> 좌하향 대각선(/)
diagonal2 = [False] * (n * 2)  # 좌상 -> 우하향 대각선(\)

def backtracking(y):
  global answer
  
  if y == n:    # 모든 행마다 배치를 마쳤다면 answer + 1 하고 return
    answer += 1
    return

  for i in range(n):
    if col[i] or diagonal1[i + y] or diagonal2[i - y + n]:   # 이미 해당위치에 퀸이 놓여있다면 공격할 수 있는 위치에 해당하므로 pass
      continue

    col[i] = diagonal1[i+y] = diagonal2[i-y+n] = True  # 퀸 배치
    backtracking(y+1)
    col[i] = diagonal1[i+y] = diagonal2[i-y+n] = False # 퀸 배치 원상복구
    
backtracking(0)
print(answer)

 

1)  n-queen 문제란, N X N 체스판에서 퀸 끼리 서로 공격할 수 없는 위치에 두는 방법의 수를 찾는 문제이다.

그럼 서로 공격할 수 없다는건 무슨 의미일까?

 

공격할 수 있다: 하나의 퀸의 위치에서 같은 행, 같은 열, 대각선 방향에 있는 퀸을 공격할 수 있다

-> 공격할 수 없다: 하나의 퀸의 위치에서 같은 행, 같은 열, 대각선 방향에 있지 않도록 배치

 

즉, 이 문제는 각 행마다 같은 열 or 대각선 방향을 피하면서 배치할 수 있는 모든 경우의 수를 찾는 문제이다.

 

2)

- 먼저, 각 행마다 같은 열에 존재하는지, ↘ 방향 대각선과 ↙ 방향 대각선에 퀸이 존재하는지를 판단할 배열을 선언한다.

- 0부터 n-1 행까지 퀸을 두면서, 같은 열이나 대각선에 퀸이 위치한다면 공격할 수 있는 방향이므로 해당 케이스는 continue를 통해 건너뛴다.

- 여기서 대각선 식이 왜 저렇게 될까?

 

↙ 방향 대각선

 

만약 현재 퀸이 (1, 3) 위치에 있다면, 1 + 3 = 4이므로 diagnoal[1 + 3]가 True라면 대각선에 퀸이 위치하고 있다고 보아도 될 것이다.

노란색 칠한곳 x, y 좌표 더하면 각각 2 + 2 = 4, 3 + 1 = 4이기 때문

즉 이를 식으로 나타내면 diagnoal1[i + y]

 

↘ 방향 대각선

만약 현재 퀸이 (1, 3) 위치에 있다면, 3 - 1 = 2이므로 diagnoa2[3 - 1 = 2]가 True라면 대각선에 퀸이 위치하고 있다고 보아도 될 것이다. 노란색 칠한곳 각각 계산하면 2 - 0 = 2, 4 - 2 = 2

다만 여기서 + n을 칠하는 이유는 i - y 가 음수가 될 수 있기 때문에 인덱스는 음수가 될 수 없으므로 양수로 만들어주기 위해서 + n

즉 이를 식으로 나타내면 diagnoal2[i - y + n]

 

- 따라서 이 식에 따라 공격할 수 없는 위치에 퀸을 배치함으로써 재귀 함수를 통해 경우의 수를 찾고, 해당 위치에 배치하는 것이 아닌 다른 위치에 배치함으로써의 조합도 찾아봐야하므로 다시 퀸 배치를 복구함으로써 알고리즘을 실행한다.