1 minute read

9663번 : N-Queen

문제 링크

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

문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

문제풀이

참고한 문서 : https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-9663-N-Queen-%ED%8C%8C%EC%9D%B4%EC%8D%AC

퀸 하나를 놓을 경우 다음 퀸은 아래의 칸들은 놓을 수 없다.

  1. 같은 행, 같은 열은 놓을 수 없음
  2. 왼쪽 대각선은 놓을 수 없음
  3. 오른쪽 대각선은 놓을 수 없음

따라서 위의 조건들은 아래처럼 구현할 수 있다.

  1. visitedCol -> 같은 행, 열의 방문정보 저장
  2. visitedLeftDiag -> 왼쪽 대각선의 방문정보를 저장, 행과 열의 합이 같은 칸들은 왼쪽 대각선으로 이어지는 칸들임
  3. visitedRightDiag -> 오른쪽 대각선의 방문정보를 저장, 행 빼기 열이 같은 칸들은 오른쪽 대각선으로 이어지는 칸들임, 다만 여기서는 음수값도 나오기에 N-1로 offset을 줌
def put_queen(k) :
    global count

    # 만약 놓은 퀸의 개수가 N과 동일하면 count+1 이후 리턴
    if k == N : 
        count += 1
        return

    # 0 ~ N까지의 범위를 반복
    for i in range(N) :
        
        # 만약 같은 행/열, 같은 왼쪽 대각선, 같은 오른쪽 대각선이 아닐 경우
        if not visitedCol[i] and not visitedLeftDiag[k+i] and not visitedRightDiag[(N-1)+(k-i)] :
            # 방문 정보 True로 갱신
            visitedCol[i] = True
            visitedLeftDiag[k+i] = True
            visitedRightDiag[(N-1)+(k-i)] = True

            # 재귀 진행
            put_queen(k+1)

            # 방문 정보 False로 원복
            visitedCol[i] = False
            visitedLeftDiag[k+i] = False
            visitedRightDiag[(N-1)+(k-i)] = False


N = int(input())
count = 0

visitedCol = [False] * N
visitedLeftDiag = [False] * (2*(N-1)+1)
visitedRightDiag = [False] * (2*(N-1)+1)

put_queen(0) 

print(count)

Comments

You May Also Enjoy