백준 9663) N-Queen (골드.4)

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

9663번: N-Queen

 

 

 

문제의 조건은 다음과 같으며 백트래킹을 이용하여 퀸을 놓을 수 있는 모든 경우의 수를 찾는 것이다. 

1) 같은 열에 퀸이 없을 것

2) 같은 행에 퀸이 없을 것 

3) 퀸의 대각선(오른쪽, 왼쪽)으로는 다른 퀸을 위치하지 않을 것 

 

 

이 문제는 python3로 풀때 계속해서 시간초과가 났기 때문에 해결방법을 찾지 못했다 😭 

두번 모두 pypy로는 성공하였다 😭

 

내가 처음에 푼 코드는 다음과 같다. 이것이 다음에 확인한 코드보다 메모리도 적게 사용하고 시간도 더 빨랐다. 

행과 열, 오른쪽 대각선, 왼쪽 대각선 정보를 담을 배열들을 만들고 해당 부분에 놓을 수 있는지를 확인할 수 있도록 하였다. 

여기서 대각선을 설명하자면 오른쪽 대각선이 같은 부분들언 행+열의 값이 같은 값을 띄며 [0, 1, 2, 3, ... 2n-1]까지의 값을 같는다.

왼쪽 대각선의 경우 i-j의 값이 같은 같은 값들이며 여기서 값이 [-(n-1), -(n-2), ...,0, 1, 2, ..., n-1]의 모양새를 띄기 때문에 인덱스를 사용하기 위해서 n-(i-j)-1을 사용하도록 하였다. 

global n, board, check_row, check_col, check_right_diag, check_left_diag, answer
n = int(input())
answer = 0
board = [[False]*n for _ in range(n)]

check_row = [False]*n
check_col = [False]*n
check_right_diag = [False]*(2*n-1)
check_left_diag = [False]*(2*n-1)


def isPossiblePosition(i, j) :
    global n, board, check_row, check_col, check_right_diag, check_left_diag
    if board[i][j] == True:
        return False
    if check_col[j] == True:
        return False
    if check_row[i] == True:
        return False
    if check_right_diag[i+j] == True:
        return False
    if check_left_diag[n-(i-j)-1] == True:
        return False
    return True

def play_queen(i, j, isPut):
    global n, board, check_row, check_col, check_right_diag, check_left_diag
    board[i][j] = isPut
    check_row[i] = isPut
    check_col[j] = isPut
    check_right_diag[i+j] = isPut
    check_left_diag[n-(i-j)-1] = isPut

def find_case(depth):
    global answer, board, n, check_row, check_col, check_right_diag, check_left_diag
    if depth == n:
        answer += 1
        return 
    for col in range(n):
        if isPossiblePosition(depth, col):
            play_queen(depth, col, True)
            find_case(depth+1)
            play_queen(depth, col, False)
    return 

find_case(0)

print(answer)

 

 

코드가 생각보다 길고 복잡해져 검색해보니 행-행 = 열 - 열 이면 같은 대각선에 있음 을 이용하도록 변경하였다. 여기서 col에 존재하는 가 는 visited배열을 이용해서 해당 column에 있는지 확인하도록 하였다. 

global n, board, check_row, answer
n = int(input())
answer = 0
board = [0]*n
visited = [False]*n

def isPossiblePosition(depth) :
    global n, board
    for row in range(depth):
        if abs(depth-row) == abs(board[depth]- board[row]):
            return False
    return True

def find_case(depth):
    global answer, board, n
    if depth == n:
        answer += 1
        return 
    for col in range(n):
        if visited[col] == False:
            board[depth] = col
            if isPossiblePosition(depth) :
                visited[col] = True
                find_case(depth+1)
                visited[col] = False
    return 
    
find_case(0)

print(answer)