[백준 9663번] N-Queen in python

문제

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

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

입력

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

출력

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

 

예제 입력 1

8

예제 출력 1

92

 

 

---

이 문제는 기존의 프로그래머스에서도 다뤘던 문제여서 금방 풀 줄 알았다...

그런데 기억이 안나...ㅜ

DFS와 재귀를 이용하여 푸는 문제.

def check(lst,row):
  for i in range(row):
    if lst[i]==lst[row] or i-lst[i]==row-lst[row] or i+lst[i]==row+lst[row]:
      return False
  return True

def N_queen(lst, row):
  count=0
  if len(lst)==row:
    return 1
  
  for col in range(len(lst)):
    lst[row]=col
    if check(lst,row):
      count+=N_queen(lst,row+1)

  return count

import sys
n=int(sys.stdin.readline())
print(N_queen([0]*n,0))

먼저 N_queen 재귀 함수를 만든다.

재귀함수를 만들기 때문에 반드시 if문으로 재귀를 끝낼 조건을 만들어 준다.

 

다음으로 행(row)의 열을 차례대로 넘길 for문을 만든다.

그 뒤 행(row)을 인덱스로 열 값을 리스트의 요소로 넣는다.

(즉 2차원 리스트가 아닌 1차원 리스트로 행은 인덱스로 열은 그 리스트의 요소로 쓰인다.)

 

행에 대응하는 열이 들어갔으므로 이전 행에 이것과 일치하는게 없는지를 체크해줘야한다.

check함수를 만들어서 그 안에 for문을 만든다. for문으로 행의 0부터 방금 넣었던 행-1까지 탐색을 해준다.

• 먼저 같은 열에 들어가면 안되니, lst[i]==lst[row] (여기서 i는 0~i-1이고 row는 현재 행이다)
• 남동쪽으로 뻗는 대각선 lst[i]-i==lst[row]-row
• 남서쪽으로 뻗는 대각선 lst[i]+i==lst[row]+row

이 3가지에 포함되면, 이번 행에 들어간 col값은 이전 queen들의 이동 동선과 겹쳐지게 되므로 경우의 수에 제외된다.

만약 위 3가지 경우에 제외된다면, row+1해서 N_queen함수로 다시 한번 들어가게 된다. 그러면 다음 행에서 예전 row에 해당되지 않는 col값을 찾고, 또 이것이 맞다면 계속해서 재귀적으로 N_queen함수를 들어가게 된다.

결국 row가 n이 될 때 동안 값을 찾았다면 문제에서 말하는 조건에 충족되므로 return 1을 받게 되고, count변수에 +1이 적립된다.

 

하지만 check함수에 걸려진다면(전의 행에 포함되는 열값들이 있음) 재귀함수는 돌아가지 못하므로 다음 열로 넘어가게 된다. 그열에서 조건에 맞는다면 재귀가 돌아갈 것이고, 그 열에도 조건에 맞지 않는다면 다음 열로 넘어간다.

만약 이 행(row)에 모든 열이 check함수를 True로 만들지 못했다면 count는 그냥 0이 되어 return된다.

 

 

 

---

예를 들자. n=4일때,

N_queen(row=0)

1. lst[row=0]=0, check=True, N_queen(row=1) 재귀함수 작동
   1. lst[row=1]=0, check=False(lst[row=0]과 같음), 다음 열로 넘어감
   2. lst[row=1]=1, check=False(lst[row=0]의 남동쪽 대각선에 포함), 다음 열로 넘어감
   3. lst[row=1]=2, check=True, N_queen(row=2) 재귀함수 작동
      1. lst[row=2]=0, check=False(lst[0]과 같음), 다음열로 넘어감
      2. lst[row=2]=1, check=False(lst[1]의 남서쪽 대각선에 포함), 다음열로 넘어감
      3. check=False(lst[1]과 같음), 다음열로 넘어감
      4. check=False(lst[1]의 남동쪽 대각선에 포함), 다음열로 넘어감
      5. row=2에서의 for문을 모두 거쳤음에도 불구하고 재귀함수를 동작하지 못했으므로 count=0인 상태로 반환
   4. lst[row=1]=3, check=True, N_queen(row=2)재귀함수 작동
      1. lst[row=2]=0, check=False
      2. lst[row=2]=1, check=True, N_queen(row=3) 재귀함수 작동
         1. lst[row=3]=0, 다음열 넘어감
         2. lst[row=3]=1, 다음열
         3. lst[row=3]=2, 다음열
         4. lst[row=3]=3 다음열
         5. row=3에서의 for문을 모두 거쳤음에도 불구하고 재귀함수 동작 못했으므로 count=0으로 반환
      3. lst[row=2]=2, 다음열
      4. lst[row=2]=3, 다음열
      5. row=2에서 for문 거쳤음에도 불구하고 재귀함수 동작 못했으므로 count=0반환
   5. row=1에서 for문ㅇ 거쳤음에도 불구하고 재귀함수 동작x, count=0반환
2. lst[row=0]=1,check=True, N_queen(row=1) 재귀함수 작동
   
   1. 이런식으로 계속 돌아간다.
   2.   ~
   3. ~ 
      1.    ~
      2.  ~~~