백준 9633 N-Queen

백준 9633 알고리즘 연습

해당 문제는 백트래킹을 사용하여 푸는 문제다.
가능한 모든 경로를 찾아봐야하지만 일반적인 dfs로 푼다면 시간초과가 되기 때문에
중간 중간 확인을 하면서 문제와 맞지 않는 경우들은 모든 경로를 찾을 때 포함되지 않도록 하는 것이다.

백트래킹을 사용해서 모든 경로를 확인하면 시간적으로 덜 걸리는 것을 알 수 있다.

n = int(input())

result = 0

def check(visitied, depth):
  global result 
  for number in range(n):
    if number in visitied:
      continue
    if find_queen(visitied, depth, number):
      if depth == n-1 :
        result+=1
      else:
        visitied[depth] = number
        check(visitied, depth+1)
        visitied[depth] = -1
        
def find_queen(visitied, depth, queen_row): 
  for v in range(depth):
    if abs(visitied[v] - queen_row) == abs(v - depth):
      return False
  return True       


for i in range(n):
  visitied = [-1 for _ in range(n)]
  visitied[0] = i
  check(visitied, 1)

if n == 1:
  result = 1
  
print(result)    

파이썬을 활용해서 문제를 풀었다.

알고리즘의 시간을 줄이기 위해서 노력을 하느라 해당 문제를 푸는데 시간이 많이 소요되었다. 그리고 문제를 다 해결해도 '틀렸습니다' 만 결과로 나와서 당황하고 오류를 찾는데도 시간이 많이 소요되었다.

결과적으로 원인은 n=1 일때 result 가 1로 나온다는 것을 제대로 처리해주지 못했기 때문이다.