백준 # 9663 N-Queen (파이썬)

백트래킹 이해

• N-Queen은 백트래킹의 대표 문제로, 백트래킹이란 해를 찾기 위하여 가능한 경로를 깊이 우선 탐색 방법(DFS)으로 탐색하는 방법을 말한다.
• 백트래킹 구현은 두 부분으로 나누어 이해해볼 수 있다.
  1. 종료 조건
  • DFS는 재귀를 통해 구현되는데, 이 때 무한 재귀를 방지하는 종료 조건이 필요하다.
  • 종료 조건은 다음과 같이 구현할 수 있다.

    			if 종료조건: 
    return (선택사항)
    			```

  • 이 때 return값은 문제에 따라 있을 수도, 없을 수도 있다.
  • N-Queen 문제의 경우 return값이 없다. 이 문제에서 백트래킹 함수는 i번째 퀸이 놓일 수 있는 자리를 재귀를 통해 가보고, 중간에 막히지 않고 n번째 퀸까지 놓일 수 있는 배치가 있다면 cnt 변수(가능한 배치 개수)를 추가하기 때문에 함수 자체의 return값은 필요하지 않다.
  2. 백트래킹 반복문
  • 재귀를 수행하는 부분이다.
  • 관건은 '가능해보이는 퀸의 자리'를 최적의 방법으로 조건화해야 한다는 것이다. (Brute Force처럼 다 보려고 하면 시간복잡도에 걸릴 확률이 매우 높다. 재귀가 들어가기 때문에 시간복잡도가 O(n!)이기 때문이다.
  • 이 문제에서 가능한 방법 한 가지는 퀸을 한 row에 한개만 배치하는 것이다.
  • 해가 될 가능성이 있다면 재귀를 통해 그 다음 깊이로 들어가 탐색을 하고, 끝까지 탐색을 한 후에는 pop()을 통해 원상태로 복구한 뒤 다음 가능성을 탐색한다.

    			for 반복조건:
    				if 해가 될 가능성 판별조건. 최적화해야 하는 부분!:
        	(선택사항)
            재귀
            pop()
            (선택사항)
    			```