[백준] N-Queen

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

9663번: N-Queen

백 트래킹을 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, N이 주어질 때, N*N의 체스판에 N개의 Queen을 배열하는 가짓수를 return해야 합니다.

 

<Solution>

사실 이전에 프로그래머스를 통해 해결한 적이 있는 문제입니다.

https://life318.tistory.com/5

[프로그래머스] N-Queen

하지만 코드를 다시 작성해 보았고, 이전에 프로그래머스를 통해 작성한 코드가 비효율적인 것을 알게 되었고, 백준을 기준으로 다시 설명을 해보도록 하겠습니다. 

 

우선 처음 작성한 코드(백준ver) 를 먼저 살펴봅시다.(오답- 시간초과)

import sys
N = int(sys.stdin.readline().rstrip())

def is_available(chessboard, new_c):
    new_r = len(chessboard)
    for r, c in enumerate(chessboard):
        if new_r == r:
            return False
        elif new_c == c:
            return False
        elif abs(new_r-r) == abs(new_c-c):
            return False
    return True

chessboard = []
ans = 0
def check():
    global ans
    if len(chessboard) == N:
        ans += 1
        return

    for i in range(N):
        if is_available(chessboard, i):
            chessboard.append(i)
            check()
            chessboard.pop()

check()
print(ans)

체스보드에 말을 놓으면서, 체스판 각각의 row에 대해 

 

1. 만약 놓을수 있다면 놓는다.

2. 새로운 말을 놓을수 있는지 체크하고 놓을 수 있다면 놓는다. (반복)

3. 만약 놓을 수 없다면 이전까지의 말을 놓은 체스판의 상태로 돌아가 다시 놓는다.

4. 모든 row에 말이 모두 놓이는 경우가 발생하면 count 해준다.

 

위의 형태로 코드가 진행됩니다.

---

하지만 여기에서 비효율적인 부분이 존재합니다. 

말을 현재 그 위치에 놓을 수 있는지 없는지를 매번 비교하면서 check하는데 이 부분을 array 3개를 두어 관리할 수 있습니다.

 

실제 저의 구현에서 

# to check available
col = [0] * N
cross1 = [0] * (2*N - 1)
cross2 = [0] * (2*N - 1)

이렇게 3개의 array를 관리하는데,

• col의 경우 column에 대해 해당 column이 현재 말이 놓일 수 있는 상태인지, 없는 상태인지를 기록합니다. 
• cross1의 경우 대각선 방향(왼쪽 위에서 오른쪽 아래방향)에 대해 마찬가지로 상태를 기록합니다.
• cross2의 경우 대각선 방향(왼쪽 아래에서 오른쪽 위)에 대해 마찬가지로 상태를 기록합니다.

이렇게 3개의 array를 추가적으로 두고, 직접 매번 비교하지 않고 해당하는 3개의 array가 모두 Queen이 놓여도 된다고 판단하는지만 보고 결정을 해주는 형태로 바꾸었습니다. (row의 경우 구현상으로 알아서 모두 다르게 들어감)

 

실제 전체 구현은 아래와 같습니다.

import sys
N = int(sys.stdin.readline().rstrip())

# to check available
col = [0] * N
cross1 = [0] * (2*N - 1)
cross2 = [0] * (2*N - 1)

def is_available(chessboard, new_c):
    new_r = len(chessboard)
    if col[new_c] == 0 and cross1[new_r + (N-1) - new_c] == 0 and cross2[new_r + new_c] == 0:
        return True
    else:
        return False


chessboard = []
ans = 0
def check():
    global ans
    if len(chessboard) == N:
        ans += 1
        return

    for i in range(N):
        if is_available(chessboard, i):
            new_r = len(chessboard)
            chessboard.append(i)

            col[i] = 1
            cross1[new_r + (N-1) - i] = 1
            cross2[new_r + i] = 1

            check()

            chessboard.pop()
            col[i] = 0
            cross1[new_r + (N-1) - i] = 0
            cross2[new_r + i] = 0

check()
print(ans)