[백준] 9663: N-Queen

백트래킹

N-Queen

백트래킹의 대표적인 문제입니다.
먼저, 어떤 퀸도 다른 퀸에 의해 잡아먹히지 않도록 배치해야 하기 때문에
같은 열, 행, 대각선에 다른 퀸들을 놓을 수 없습니다. (문제에 왜 이런 설명이 없나요??)

backtracking 되추적

1. 임의의 집합(set)에서 주어진 기준(criterion)대로 원소의 순서 (sequence)를 선택하는 문제를 푸는데 적합합니다.
2. 트리 자료 구조의 변형된 DFS입니다 (한번 갈 때 깊이 우선 탐색을 하니까요)
3. 모든 문제를 해결할 수는 없으나 많은 경우에 문제를 해결할 수 있습니다.
   예를 들면, n-queen, 부분 집합의 합, 0-1배낭 문제 등이 있습니다.

미로찾기 문제를 예시로 찾아왔습니다
퀴즈] 프로그래머를 위한 문제 #3 - 미로 찾기 :: "엄준일"과 함께하는 소프트웨어를 위한 플랫폼 이야기
프로그래머를 위한 문제래요.. ㅋㅋ
차에 탄 강아지가 허니를 찾으러 가려면 어떻게 해야 할까요
이 문제는, 두가지 방법으로 해결할 수 있습니다.
1. 스택을 이용해서 갈 수 있으면 push 갈 수 없으면 pop을 한다.
2. 트리를 이용하여 DFS preorder(전위순회)를 사용하면 된다.
그런데 이렇게 완전 탐색을 하면 시간이 너무 오래걸리겠죵

그래서 백트래킹에는 상태공간 트리와 DFS를 이용합니다.
여기서 백트래킹에 사용되는 트리를 상태공간 트리라고 한다.
상태 공간: 해답을 탐색하기 위한 탐색 공간
상태 공간 트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해석한 것
최적화는 모든 상태 트리를 DFS를 돌면서 시킬 수 있다.

백트래킹

1) 상태 공간 DFS: 브루트포스(시간이 오래걸림)
2) 해당 노드의 하위트리를 방문하지 않고 부모노드로 돌아감(promising -> pruning)

유망함(promising)

현재 상태에서 더 진행해도 소용이 없다 -> 유망하지 않다.

방문중인 노드에서 하위노드가 해답을 발견할 수 있다. -> 유망

가지치기(pruning)

백트래킹과 가지치기는 관련이 있습니다.
백트래킹: 상태공간 트리 DFS
유망한지 체크하고 유망하지 않다면 가지치기 후 백트래킹한다.
이때 유망하지 않은 것의 하위트리를 더이상 방문하지 않는것을 가지치기라고 한다.

일반적인 백트래킹 알고리즘 수도코드

void checkNode(node v){	
	node u;
    	if promising(v)){
    		if (v 에 해답이 있다면){
        		해답출력
         	}
       		else:
       	    		for (v의 모든 자식 u에 대해){
            			checkNode(u);
             		}

백트래킹 구현

1. 상태 공간 트리를 실제로 구현 할 필요는 없습니다.
2. 현재 조사중인 가지의 값에 대한 추적이 필요합니다.
3. 상태 공간 트리는 암묵적인 존재이다.

N-Queen

8-queen(n=8) 일반화
1. n*n 체스보드에 n개의 퀸 배치
2. 어떤 퀸도 다른 퀸에 의해 잡아먹히지 않도록 배치
3.같은 열, 행, 대각선에 다른 퀸들을 놓을 수 없다.
"임의의 집합(set)에서 주어진 기준(criterion)대로 원소의 순서 (sequence)를 선택하는 문제를 푸는데 적합하다"
임의의 집합: 체스 보드에 있는 n^2개의 가능한 위치
기준 : 새로 놓을 퀸이 다른 퀸을 위협하지 않는가?
원소의 순서: 퀸을 놓을 수 있는 n개의 위치

일단 기본 가정으로 같은 행에는 놓을 수 없다고 합시다.

유망함수(promising) : 같은 열이나 대각선에 놓이는지 확인
1. 같은 열 체크 :
col[i] : i번째 행에서 퀸이 놓여있는 열의 위치
col[k]: k번째 행에서 퀸이 놓여있는 열의 위치
col[i] == col[k] :같은 열에 놓이므로 유망하지 않다.
2. 대각선 체크
abs(col[i] - col[k]) == abs(i-k)

시간초과

def n_queens(i, col):
	global cnt
	n = len(col) -1
	if (promising(i, col)):
		if (i == n):
			# print(col[1:n+1])
			cnt += 1
		else:
			for j in range(1, n+1):
				col[i+1] = j
				n_queens(i+1, col)
def promising(i, col):
	k = 1
	flag = True
	while (k < i and flag):
		if ((col[i] == col[k]) or (abs(col[i] - col[k]) == (i-k))):
			flag = False
		k += 1
	return flag
cnt = 0
n = int(input())
col = [0] * (n+1)
n_queens(0, col)
print(cnt)

통과

import sys
def n_queens(i, col):
	global cnt
	n = len(col) -1
    	# 만족하는 조건에 다다르면 함수 return 
	if (promising(i, col)):
		if (i == n):
			# print(col[1:n+1])
			cnt += 1
			return  # 중요
		else:
			for j in range(1, n+1):
				col[i+1] = j
				n_queens(i+1, col)
def promising(i, col):
	k = 1
    	#얘도 마찬가지 
	while k < i :
		if ((col[i] == col[k]) or abs(col[i] - col[k]) == i-k):
			return False
		k += 1
	return True
cnt = 0
n = int(sys.stdin.readline().rstrip())
col = [0] * (n+1)
n_queens(0, col)
print(cnt)