[Python] 백준 9663번 문제, N-Queen

<문제 링크>

 

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

9663번: N-Queen

 

---

<풀이>

 

N-Queen 문제는 위 그림과 같이 2차원 리스트를 사용해서 마지막 행까지 정상적으로 퀸이 놓여진다면 count++를 하고, 그렇지 않다면 다음 경우를 실행한다.

 

2차원 리스트로 사용해 하나씩 조건을 따진다면 코드가 복잡해질 것 같아 찾아보던 중에

1차원 리스트에서 인덱스 번호를 행으로, 인덱스 값을 열로 지정해 사용할 수 있었다.

그래서 위 그림과 같이 표현할 수 있다.

그럼 여기서 문제가 발생하는데 좌우로는 판단이 되지만, 대각선은 구분할 수 없다.

대각선을 구분하기 위해서는 수식을 이용해야 하는데,

(놓으려는 자리의 행 - 모든 행 중 하나(0~마지막)) == |(놓으려는 자리의 열 - 모든 행 중 하나의 열)|

이라면 대각선 상에 있다.

위 이미지로 예시로 보자면, 빨간 점에 두려고 했을 때 왼쪽 상단 파란 점의 대각선 상에 있는데

(2 - 1) == (1 - 0) -> 1 == 1 -> True

이기 때문에 빨간 점에 둘 수 없다.

 

따라서 이런 조건으로 퀸을 놓아 마지막 행까지 정상적으로 놓아진다면 count++,

그렇지 않다면 다음 경우를 수행하면 된다.

 

---

<코드>

count: 조건에 맞게 놓을 수 있는 경우의 수

board[]: 인덱스 번호 == 행, 인덱스 값 == 열을 의미하는 리스트

visited[]: 방문 여부 체크 리스트

---

import sys

def logic(n):
    if n == N: # 마지막까지 탐색 완료
        global count # 전역변수 설정

        count += 1 # 값 증가
    else:
        for i in range(N):
            if visited[i]:
                continue

            board[n] = i # (n, i)에 퀸 올리기

            if check(n): # 퀸 놓기 조건에 맞다면
                visited[i] = True
                logic(n+1) # 다음 행으로 넘어가긴
                visited[i] = False


def check(n):
    for i in range(n):
        # 이미 놓여진 퀸과 같은 열이거나 대각선 상에 있는지 확인
        # (행끼리의 차 == 열끼리 차의 절대값)이 True면 대각선 상에 있는 것임
        if (board[n] == board[i]) or (n - i == abs(board[n] - board[i])):
            return False

    return True


if __name__ == '__main__':
    N = int(sys.stdin.readline())
    count = 0
    board = [0 for _ in range(N)] # 인덱스 번호 == 행, 인덱스 값 == 열
    visited = [False for _ in range(N)]

    logic(0)
    print(count)