bj9663 N-Queen

N-queen 문제

사실 42서울에서 10-queen을 이미 c로 풀어봤고 그걸 python으로 다시 푼 것이다.

음.. 근데 나는 진짜 완전 잘 했는데 시간 초과가 남... 근데 backtracking을 이 방법 이상으로 구현할 수 없어서 인터넷 찾아보고 pypy3로 제출하니까 통과 됨... 아.. 진짜 c언어가 겁나 빠른 언어긴 한가보다...

우선 접근을 이렇게 했다.

1. queen의 위치를 담을 list가 있다고 생각했고 index를 행으로 생각했다.

2. 각 index에 해당하는 value들은 열에 해당한다!

3. 그렇다면 행을 loop를 통해 늘려가면서 해당 행의 n번째 열에 queen을 놓아야겠다.

4. 놓을 수 있는 조건도 생각해야겠네?

우선 3번부터 생각했다. 종료조건이 있어야겠고 종료 조건에 해당하지 않으면 퀸을 놓으면서 다음 행으로 넘어가는 loop가 필요했다. 근데 퀸을 놓으려면 조건이 필요했다.

def queen(_board, x):
    y = 0
    if x == N:
        queen.count += 1
    else:
        for y in range(N):
            if check_board(_board, x, y) == 1:
                _board.append(y)
                queen(_board, x+1)
                _board.pop()

4번을 생각하는 것이 핵심이었다.
퀸은 같은 열에 놓일 수 없고 and 대각선에 놓일 수 없다!
따라서 이것을 판단하는 check 함수를 하나 만들었다.
check_board함수의 역할은 해당 행과 열을 동시에 전달해서 이 위치에 놓을 수 있는지 board를 확인해주는 함수이다.

def check_board(_board, x, y):
    num = 0
    while num < x:
        temp = _board[num] - y
        if temp < 0:
            temp = -temp
        if(_board[num] == y) or (temp == x - num):
            return 0
        num += 1
    return 1

그래서 전부 다 합쳐보면 이렇게 구현할 수 있다!

def queen(_board, x):
    y = 0
    if x == N:
        queen.count += 1
    else:
        for y in range(N):
            if check_board(_board, x, y) == 1:
                _board.append(y)
                queen(_board, x+1)
                _board.pop()


def check_board(_board, x, y):
    num = 0
    while num < x:
        temp = _board[num] - y
        if temp < 0:
            temp = -temp
        if(_board[num] == y) or (temp == x - num):
            return 0
        num += 1
    return 1


N = int(input())
queen.count = 0
board = []
queen(board, 0)
print(queen.count)

근데 c언어로 하면 음... 배열 크기를 그냥 15로 잡고 하나? 아니면 동적할당 하려나? 백준 동적할당해도 되나?? ㅋㅋㅋ 모르겠네 내일 자고 일어나서 한번 해봐야겠다.