[Python] 백준 9663 : N-Queen

문제

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

[ 문제 조건 ]

• 1 ≤ N < 15
• 출력 : 서로 공격할 수 없게 놓는 경우의 수
• 백트래킹 문제 → 개념을 알고 있어야 함

[ 해결순서 ]

1. 체스판에 퀸을 놓기위한 조건은 퀸의 가로, 세로, 대각선에 위치한 곳에 두면 안된다.
2. 백 트래킹 문제에선 퀸을 놓을 때 직전의 열에 두지 않는다고 한다. ( 중복제거를 위해 )
3. 하나의 행에 하나의 퀸만 놓을 수 있다.
4. 그렇다면 N * N개의 경우의 수가 존재 할 텐데 이 중에서 서로 공격하지 않게 놓는 경우의 수를 구해야한다.
5. nqeen()은 퀸을 오른쪽 행으로 하나씩 옮기면서 경우의 수를 확인하고
6. check()로 행은 비교할 필요가 없고 (3번참고) 같은 열인지, 대각선상에 있는지 비교한다.
7. nqeen()에서 퀸이 끝 행까지 도달했다면 경우의 수(count)를 하나 추가해준다.
8. 이를 재귀적으로 반복해서 값을 구한다.

[ 예제 직접구현 ]

✏️한줄평

: 백 트래킹이 무엇인지 개념을 파악할 수 있었다. 처음 접한 개념이라 낯설게 느껴져 시간소요를 많이 했지만 다시 복습하거나 다른 비슷한 유형 풀면서 익숙해져야겠다.

---

코드

	N = int(input())
	board = [0 for _ in range(N)] #체스판
	count = 0 #퀸 N개를 서로 공격할 수 없게 놓는 경우의 수
	#다음행만 가능 -> 중복 제거를 위해
	#인덱스 행, board[x]은 열
	def nqueen(x):
	global count
	if N == x: #체스를 끝 행까지 도달했을 때
	count += 1
	else:
	for i in range(N):
	board[x] = i #x번째 행, i열에 퀸 놓음
	if check(x): #행,열,대각선이 같은 위치에 없다면
	nqueen(x+1) # 해당 경우보다 한단계 깊이 재귀적으로 또 확인
	def check(val):
	for i in range(val): #열, 대각선 같은지 비교
	if board[val] == board[i] or abs(board[val] - board[i]) == val - i:
	return False
	return True
	nqueen(0)
	print(count)

view raw BOJ9663.py hosted with ❤ by GitHub