[백준] 9663 - N_Queen

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

9663번: N-Queen

문제 한줄 이해

- N*N 격자판에서 퀸 N개가 서로 공격할 수 없도록 놓는 경우의 수 구하기

생각난 풀이

1번째 방법: 싸피 코딩테스트 준비하면서 swea사이트에서 풀었던 문제와 비슷하다고 생각이 났다.

우선 이전 줄에 퀸을 놓았을때 다음 줄에 어떤 칸에 퀸을 놓을수 있는지 판단하면 된다. 어떤 칸에 놓을 수 있는지 판단 아이디어는 다음과 같다.

퀸의 특성을 보면 대각선과 상하좌우로 이동이 가능한 특징을 가지고 있다.

하지만 나는 첫줄부터 세우면서 갈것이기 때문에 같은 열에 있는지, 왼쪽 아래 대각선에 있는지, 오를쪽 아래 대각선에 있는지 판단하면 된다. 그래서 같은열에 있다는 것은 y좌표가 같은것은 금방 캐치할 수 있고 대각선은 한번 규칙을 찾아봐야한다. 규칙을 보면 다른 두 좌표가 대각선에 위치한다는 것은 |x1-x2| =|y1-y2|인 경우를 알 수 있다!! 따라서 어떤 위치에 놓았는지 리스트에 저장하고 백트래킹을 통해 경우의 수를 체크하면 된다.

import sys
n = int(sys.stdin.readline())

def back(depth):
    global cnt
    #n번째 줄에 도달하면 경우의수 +1
    if depth == n:
        cnt +=1
        return
    
    # 다음 좌표 depth,i
    for i in range(n):
        flag = True
        #저장된 좌표를 꺼내서 확인
        for a,b in queen:
            # 조건문에 걸리면 그자리에 놓을수 없다.
            if i == b or (abs(depth-a) == abs(i-b)):
                flag = False
                break
        #저장된 좌표랑 모두 비교했을때 문제 없다면 재귀 실행
        if flag == True:
            queen.append((depth,i))
            back(depth+1)
            queen.pop()
queen = []
cnt = 0
for i in range(n):
    #첫줄에 각 자리에 모두 두면서 백트래킹 진행
    queen.append((0,i))
    back(1)
    queen.pop()
print(cnt)