백준 9663번 N-Queen (1)

2021년 06월 26일

---

백트래킹 공부하기(3)

n과 m 문제 1~4번을 풀었기 때문에 나는 바로 N-Queen 문제에 도전한다

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

N*N 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다

N이 주어지면 퀸을 놓는 방법의 수를 구해야 한다

이 문제는 N의 범위가 1 ~ 15 라서 15중 for문을 쓰면 어찌어찌 답은 나오긴 하겠지만

그걸 원하는 것은 절대 아닐 것이다

당연히 백트래킹 대표문제인데 ? 그냥 해본 소리입니다

결과적으로 지금은 문제를 푸는데 성공을 했지만

내가 실패한 과정도 기록해놓으려고 한다

나중에 봤을 때 재미있을 거 같아서

일단 내가 이 문제를 풀면서 기록했던 내용들...

먼저 2가지 방법을 생각했었다

1. 퀸을 놓은 자리를 2차원 배열로 해서 기록한다
2. 1차원 2개로 기록한다

먼저 1번 방법을 채택하고 퀸을 놓으면 더 이상 놓을 수 없는 자리를 모두 2차원 배열에 기록했다

n과 m 문제를 풀며 터득한 백트래킹 개념을 활용하며 퀸을 놓아가기 시작했다

더 이상 놓을 수 없을 땐 돌아오면서 퀸을 회수하는데 이때는 다시 퀸을 놓으면서 기록했던 내용들을 지웠다

처음에는 그냥 1로만 기록했다가 겹치는 부분에서 제대로 작동하지 않는다는 것을 깨닫고 누적을 시켰다

그런데 당연하게도 시간이 오지게 오래걸렸다

1차원 2개로도 시도해보려 했는데 대각선을 어떻게 할지 떠올리지 못했다

여기까지 시도했던 코드

from sys import stdin

n = int(stdin.readline())

check = [[0 for i in range(n)] for j in range(n)]
count = 0

def Nqueen(k,x):
  global count
  if k == n:
    count+=1
    return
  else:
    for i in range(x,n):
      for j in range(n):
        if check[i][j] == 0:
          checkmap(i,j)
          Nqueen(k+1,x+1)
          uncheckmap(i,j)

def checkmap(i,j):
  for x in range(n):
    for y in range(n):
      if x==i or y==j or i+j==x+y or i-j==x-y:
        check[x][y] += 1

def uncheckmap(i,j):
  for x in range(n):
    for y in range(n):
      if x==i or y==j or i+j==x+y or i-j==x-y:
        check[x][y] -= 1

Nqueen(0,0)
print(count)
# 1. check를 2차원 배열로?
# 2. 1차원 2개로 방법이?
# 지금 문제점 -> uncheckmap은 방금전에 체크했던거만 제거해야하는데
# 지금은 걍 싹다 밀어버림 망함
# 누적으로 해결
# 근데 제대로 작동은 안함 뭐가 문제?

# 리스트 2개로 하면 x,y 에 대해서
# 수직 수평 방향은 각 리스트에 1인지
# 확인하면 끝
# 대각선 방향이 문제
# x+y랑 똑같은 곳이 1인가?
# x-y랑 똑같은 곳이 1인가?

# 중복이 생김
# 중복 제거해야함
# 이전에 탐색했던 줄 다음부터
# 탐색을 해서 중복은 제거함
# 근데 2차원으로 해서 그런지
# 시간이 오지게 오래걸림