백준 9663. N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

일전에 42서울 피신 중에 접한 적 있는 문제. 이 때 백트래킹이라는 알고리즘의 존재를 처음 알았다 . . .

유명한 문제기도 하고, 파훼법도 생각보다 간단하다.

백트래킹 문제의 핵심은 아무래도 적합성 검사 알고리즘이니깐 그 부분만 잘 구현하면 된다.

 

우선 기본적인 아이디어는 다음과 같다.

1. 얼핏 보면 2x2 List가 필요할 것 같지만, 일차원 리스트로 충분하다.

- 어차피 한 row에 퀸이 두 개 이상 들어가면 그 판은 불합격이므로 한 row에 한 퀸이 들어간다는 가정 하에 알고리즘을 짤 수 있다.

이 때 인덱스 값이 x값이 되고, row[x]에 들어있는 값이 해당 row의 y값이 된다.

이렇게 일차원 리스트로 문제를 접근함으로서 난이도와 검사 알고리즘이 대폭 하락한다 !

 

2. 검사 알고리즘은 row, 대각선만 검사하면 된다.

- 일차원으로 문제를 푼 덕에 col (가로) 중복은 고려할 필요가 없다. 따라서 세로와 대각선을 검사해주면 되는데, 세로는 i in arr 식으로, 대각선은 서로 다른 두 퀸을 연결하는 직선의 기울기를 이용해서 검사해줄 수 있다. y-y'/x-x'임을 기억하자.

 

따라서 이 두 가지로 문제를 해결한 코드는 다음과 같다.

 

n = int(input())

row = [0] * n
count = 0

#세로와 대각선 체크
def check(x):
	global arr
	for i in range(x):
		if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i): #직선의 기울기 +-1 == |y-y'| = |x-x'|
			return False
	return True

def dfs(x): #x값은 row의 인덱스를 뜻한다
	global count
	if x == n:
		count += 1
		return
	for i in range(1, n+1):
		row[x] = i
		if check(x) == True:
			dfs(x + 1) 
dfs(0)
print(count)