** 알고리즘 오답노트 19 (백준 - 9663)

박경준·2021년 6월 21일
0

알고리즘 문제풀이

목록 보기
22/24

N-Queen

재귀함수의 개념은 이해가 되고, 문제풀이 아이디어도 떠오르는데 코드로 표현하는게 어렵다...
반복 안에 반복을 구현할때 재귀 함수를 쓰는데, 안쪽 반복을 재귀적으로 표현해야 한다.

import sys
num = int(sys.stdin.readline())
row = [0] * num # 인덱스가 행, 값이 열
result = 0
def validation(x):
  for i in range(x):
    if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
      # 같은 열이거나, 대각선상에 있으면 다음 행으로 넘어갈 필요가 없어지므로 false를 줘서 recursive를 실행 안함.
      return False
  return True # 상위 행들을 모두 확인하며 하나도 false가 걸리지 않아야 비로소 true를 받을수 있음.
def recursive(x):
  global result
  if x == num:
    result += 1
  else:
    for i in range(num):
      row[x] = i
      if validation(x):
        recursive(x+1)
        
recursive(0)
print(result)
profile
빠굥

0개의 댓글