N-Queen

N-Queen
연습문제
778명 완료

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

유명하고 오래된 알고리듬 문제다. 
위키백과에도 나온 문제라는 사실을 알고 있다면.. 이런 장난을 칠 수도 있다.. 

solution = lambda n: (1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200)[n - 1]

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.6MB)
테스트 3 〉	통과 (0.04ms, 10.8MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.04ms, 10.8MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.04ms, 10.7MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)

https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전

check로 가지를 쳐가면서 깊이 우선 탐색을 한다.

board 배열은 1차원 배열을 사용하였다.
board[row] = col의 느낌으로..
[0][1]에 퀸이 있다면 board[0]=1로 표현할 수 있다. 
이렇게 하는 이유는 속도 때문. 

체크 루틴을 보면

반복문을 돌려서 
col에 먼저 차지한 퀸이 있는 경우 실패다. 

대각선의 경우 규칙성을 찾아야 하는데.. 
크게 어렵진 않다. 

def solution(n):
    answer = [0]
    n_queen([0] * n, 0, n, answer)
    return answer[0]


def n_queen(board, row, n, answer):
    if row == n:
        answer[0] += 1
        return
    for col in range(n):
        if check(board, row, col):
            board[row] = col
            n_queen(board, row + 1, n, answer)


def check(board, row, col):
    for r in range(row):
        if board[r] == col or (row - r) == abs(col - board[r]):
            return False
    return True

 

이런 식으로 파라미터를 줄이면 좀 더 우아하다...

def solution(n):
    return n_queen(n, 0, [0] * n)


def n_queen(n, row, board):
    answer = 0
    for col in range(n):
        if check(board, row, col):
            board[row] = col
            if row == n - 1:
                answer += 1
            else:
                answer += n_queen(n, row + 1, board)
    return answer


def check(board, row, col):
    for r in range(row):
        if board[r] == col or (row - r) == abs(col - board[r]):
            return False
    return True

 

위 코드 정도가 가독성 및 유지보수 측면에서 적당하다고 생각되지만.....
의미 없는 줄이기를 하고 싶다면...

def solution(n):
    return n_queen(n, 0, [0] * n)


def n_queen(n, row, board):
    answer = 0
    for col in range(n):
        checker = True
        for r in range(row):
            if board[r] == col or (row - r) == abs(col - board[r]):
                checker = False
                break
        if checker:
            board[row] = col
            if row == n - 1:
                answer += 1
            else:
                answer += n_queen(n, row + 1, board)
    return answer

 

억지스럽긴 하지만.. 

def solution(n, row=0, board=None):
    answer, board = 0, [0] * n if board is None else board
    for col in range(n):
        checker = True
        for c in range(row):
            if board[c] == col or (row - c) == abs(col - board[c]):
                checker = False
                break
        if checker:
            board[row] = col
            if row == n - 1:
                answer += 1
            else:
                answer += solution(n, row + 1, board)
    return answer