[Python] 9663번 N-Queen (추후 보강 예정)

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

---

 

22/09/01

 

 

클래스 3 문제 중에서 안 풀었던 문제가 있기에 풀어보았다. 백트래킹 문제 중에서 가장 유명하고 잘 알려진 문제인 N-Queen 문제이기에, 나는 당연히 이 문제를 솔루션을 보지 않고는 풀기 힘들 것이라고 생각되어서 이 문제를 유튜브 강의를 참고하여 해결하였다.

 

참고한 유튜브 강의는 아래 링크에 있다. 유튜브 강의에서 설명을 굉장히 잘 해놓았기 때문에 보고 글을 읽으면 더욱 이해가 잘 될 것이다.

파이썬으로 배우는 알고리즘 기초: 19. n-Queens 문제의 구현 - YouTube

---

 

첫 번째 접근 방식:

 

첫번째 접근 방식은 위의 영상을 보고 그대로 구현한 내용이다.

 

위에 영상을 보면 알 수 있듯이, 이 문제의 핵심은 두 가지에 있다.

 

첫 번째는 퀸을 같은 행 또는 같은 열에 놓을 수 없다는 아이디어에 착안하여, 퀸을 놓을 수 있는 체스 판을 이차원 배열이 아닌, 일차원 배열로 구현하는 것이다.

 

두 번째는 promising함수의 구현인데, 위의 영상의 경우 퀸을 같은 행에 놓을 수 없다고 가정하여 배열을 만들었기 때문에, promising함수에서 같은 열 또는 대각선에 놓여 있는지 확인하는 부분이 있어야 된다.

 

첫 번째 아이디어의 구현은 다음과 같이 진행된다.

 

col이라는 배열을 선언하는데, 여기서 인덱스 i는 행의 번호이다. 그리고 col[i]의 값은 퀸이 놓여있는 열의 번호이다.

 

서로 다른 배열의 두 원소가 있을 때, 두 원소의 값은 겹칠 수 있어도 두 원소의 인덱스는 겹칠 수 없다는 사실 때문에 이렇게 구현할 수 있는 것이다.

 

두 번째로, promising함수의 구현은 다음과 같이 진행된다.

 

위에서도 언급했듯이, col이라는 배열에서 원소의 값은 퀸이 놓여있는 열의 번호이기 때문에, 이 열의 번호가 겹치면 안 된다.

 

따라서 서로 다른 두 원소가 있을 때, 두 원소의 값은 같지 않아야 한다.

 

대각선 부분이 조금 까다로운데, 서로 다른 두 원소가 있을 때, 두 원소의 인덱스의 차이는 행의 차이이기 때문에 세로로 얼마만큼 갔냐를 의미한다.

 

두 원소의 값의 차이는 열의 차이이기 때문에 가로로 얼마만큼 갔냐를 의미한다.

 

만약 두 퀸이 같은 대각선에 있다면, 이 행의 차이와 열의 차이가 서로 같을 것이다,

 

따라서 서로 다른 대각선에 있어야 된다면 인덱스의 차이와 값의 차이가 서로 달라야만 한다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. python3으로는 통과하지 못해서 pypy로 통과하였다. 더보기를 누르면 확인할 수 있다.

# 9663번 N-Queen
# 브루트포스, 백트래킹
'''
접근 방법:
핵심은 같은 row에는 Queen을 놓지 않는다는 것임
=> 체스판을 2차원배열 대신 1차원배열로 압축 가능
col[i]를 다음과 같이 정의 한다.
col[i] = i번째 row에서 퀸이 놓여있는 column  -> 배열의 인덱스가 row가 될 수 있음

이후 우리는 promising function의 구현을 두 부분으로 나누어 한다.
1. 같은 column에 있으면 False
2. 같은 diagonal에 있으면 False

1번의 구현:
어떤 i, k에 대해(i != k)
col[i] == col[k]

2번의 구현:
어떤 i, k에 대해(i != k)
abs(col[i] - col[k]) == abs(i - k)   => 가로로 간 거리와 세로로 간 거리가 같을 때
'''
def promising(i): # i번째 row과 col[i]번째 col에 퀸을 놓았을 때 가능한지 확인하는 함수
    for k in range(1, i):
        if col[i] == col[k]:   # 세로줄 확인
            return False
        if abs(col[i] - col[k]) == i - k:  # 대각선 확인
            return False
    return True

def N_queen(i: int): # i번째 row와 col이라는 state space tree가 주어질 때 탐색하는 함수
    global num
    N = len(col)-1
    if promising(i):
        if i == N:   # 도착하면
            num += 1
        else:
            for j in range(1, N+1):
                col[i+1] = j
                N_queen(i+1)
num = 0
N = int(input())
col = [0 for _ in range(N+1)]
N_queen(0)
print(num)

 

---

 

두 번째 접근 방식:

 

python3로 통과하지 못해서, 좀 더 빠른 방법이 없을까 고민하던 중 바킹독님의 강의에서 아이디어를 얻어 문제를 해결할 수 있었다.

 

바킹독님의 아이디어는 위의 아이디어에서 1차원 배열을 사용한다는 것까지는 비슷한데, 이를 세로, 대각선에도 확장시켜서 메모리를 조금 더 사용한다는 차이점이 존재한다.

 

이때, 세로, 대각선에서 놨는지 확인하는 배열은 값으로 확인하는 것이 아니라 True와 False라는 배열로 확인한다.

 

개인적으로는 이 방법이 백트래킹이라는 이름에 걸맞게 더 직관적이고 제일 좋아 보이는 방법이라고 생각한다. 

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. python3로는 통과하지 못해서 pypy로 제출하였다. 더보기를 누르면 확인할 수 있다.

# 바킹독님의 코드 참고
def N_queen(row): # (row, 1), (row, 2), ... (row, n)까지 돌면서 둘 수 있는지 확인하는 함수
    global num
    if row == N:
        num += 1
        return
    for col in range(1, N+1): # (row, col)에 퀸을 놓을 것임
        if col_using[col] or right_up_using[col+row] or right_down_using[row-col+N-1]:
            continue
        col_using[col] = True
        right_up_using[col+row] = True
        right_down_using[row-col+N-1] = True
        N_queen(row+1) # row를 1 증가시켜서 퀸을 놓는다
        col_using[col] = False  # backtrack
        right_up_using[col+row] = False
        right_down_using[row-col+N-1] = False

num = 0
N = int(input())
col_using = [False for _ in range(N+1)]
right_up_using = [False for _ in range(2*N)]
right_down_using = [False for _ in range(2*N)]
N_queen(0)
print(num)

 

---

세 번째 접근 방식:

 

이렇게 했음에도 불구하고 python3로 통과하지 못해서....

 

그냥 문제에서 요구하는 답을 미리 계산하여 그 답만 출력하는 코드를 작성했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 숏코딩 용
print([0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184][int(input())])