백준 9663 - N-Queen

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

9663번: N-Queen

 

한 시간 넘게 투자했지만 풀지 못하였다. 반복문도 여러 개 썼는데 너무 복잡해서 제대로 풀고 있는게 맞는지 계속 의심이 갔다. 나는 처음에 n*n 보드판이므로 2차원 배열을 선언했다. 하지만 그럴 필요가 없었다. 왜 그런지는 문제 분석을 하면서 설명하도록 하겠다.

 

다른 사람의 풀이를 보니 의외로 간단했다. 두 가지 풀이법이 있었는데 나는 1번을 선택했다.

1. 1차원 배열을 선언한 후, 배열에 퀸의 위치를 담는 것

2. 1차원 배열을 2개 선언한 후 하나는 퀸의 위치, 하나는 n번째 열에 퀸이 있는지의 여부를 담는 것

 

어차피 check함수를 선언해서 같은 열/행, 대각선에 다른 퀸이 존재하는지에 대해 확인할 것이므로 굳이 리스트를 하나 더 선언하지 않는 1번 풀이법을 선택하였다.

 

풀이를 위한 알고리즘 사고는 다음과 같다.

1. N x N 보드판에 N개의 퀸을 배치하기 위해서는 반드시 하나의 행/열에 하나의 퀸만 들어갈 수 있다는 것을 알 수 있다.

=> 따라서, 1차원 배열을 선언하여 (board[x] = i => (x, i)에 위치한다는 의미) 퀸의 위치를 저장할 수 있다.

 

2. 같은 열 or 대각선에 다른 퀸이 존재하면 안된다. => check함수

같은 열 : 배열의 값이 같은 것이 있는지 확인

대각선: 퀸이 존재하는 위치의 x좌표의 차와 y좌표의 차가 같을 경우 대각선에 존재한다는 의미

 

3. 첫 번째 행에서 0~(n-1)번째 열까지 반복문을 돌면서 순차적으로 퀸을 넣어본다. (반드시 하나는 들어가므로 -)

퀸을 넣고, 퀸을 넣은 해당 행까지 반복문을 돌려 같은 줄 or 대각선에 있는 퀸이 없을 경우에만 다음 행으로 이동하여 다시 퀸을 추가하는 것을 반복 - 만약, 체크함수를 돌려서 False가 나왔을 경우, i를 증가시켜 (열을 증가) 퀸을 넣는다.

 

4. 풀이 코드에서 x는 행을 의미한다. N x N 보드판에 N개의 퀸을 배치해야 하므로 행이 N과 같아질 때마다 방법의 수를 세는 변수를 1씩 증가시킨다.

 

n = int(input())
board = [0] * n  # 보드판 생성
cnt = 0


def check(x):
    for i in range(x):  # x번째 행에 퀸을 배치했다면, x번째 행이 되기 전까지 반복문을 실행
        if board[x] == board[i] or abs(board[x] - board[i]) == abs(x - i):  # 같은 줄에 있거나 or 대각선에 존재하는 경우
            return False
    return True


def n_queens(x):
    global cnt
    if x == n:  # 퀸이 체스판 크기인 N개가 존재하는 경우
        cnt += 1  # 방법의 수 1씩 증가
        return
    else:
        for i in range(n):
            board[x] = i  # 퀸을 [x, i]에 놓겠다는 의미 = [0, i] = 0행 i열 = 맨 윗줄 i열
            if check(x):  # 같은 줄에 있거나 or 대각선에 존재하는 경우가 없을 경우(== 공격할 수 없는-)
                n_queens(x + 1)  # 다음 줄(행)에 퀸 하나를 추가


n_queens(0)  # 퀸은 모든 행에 반드시 하나씩 존재하므로 첫 번째 줄인 0부터 시작
print(cnt)