[Baekjoon]백준 9663 N-Queen(골드 4) - Python

문제설명

문제를 살펴보면 체스판 위에 퀸을 놓고 서로 공격이 불가능한 경우의 수를 찾는 문제이다

이를 해결하기 위해서 가장 먼저 들었던 생각은 2차원 배열을 함수의 인자로 전달받고, 

각 행마다 퀸을 하나씩 놓은 후에 백트래킹 방식으로 도는 방식이 떠올랐다

그러나 2차원 배열을 계속해서 사용하기에는 너무 복잡할 것 같아 1차원 배열로 해결가능한 방법을 생각해보았다

생각해보다보니 퀸은 대각선, 직선으로 이동이 가능하기 때문에 각 행, 열에는 퀸이 하나씩만 존재가능하다

이를 이용하여 1차원 배열을 활용한 코드를 작성할 수 있다

def check_attack(chess, row, col):
    for i in range(row):
        if chess[i] == col:
            return False
        if abs(chess[i] - col) == abs(i - row):
            return False
    
    return True

def sol(row):
    global cnt
    if row == N:
        cnt += 1
        return
    else:
        for col in range(N):
            chess[row] = col
            if check_attack(chess, row, col):
                sol(row + 1)

N = int(input())
chess = [0] * N
cnt = 0
sol(0)
print(cnt)

먼저 백트래킹을 사용하는 함수를 하나 만들었다 그리고 횟수를 카운트해야하므로 cnt변수를 전역변수로 선언해준다

이후에 N과 받은 인자를 비교하여 같다면 cnt를 증가시킨다 즉, 모든 행에 퀸을 배치하였는지 확인하는 부분이다

아직 퀸을 배치해야한다면(else부분), for문을 통해 row번째 행에 퀸을 col번째 열에 배치하되,

다른 퀸과 공격이 가능한지 확인하는 함수를 통해 확인하는 부분이 필요하다

공격이 불가능하다면 다음 행에도 같은 동작을 하면 된다

check부분에는 첫번째 if문에서는 같은 열에 있는지 확인하는 코드이며 두번째 if문에서는 대각선을 확인하는 코드이다

chess[i] - col, i - row 부분은 행과 열의 차이가 같은지 확인하는 코드이며, 이를 위해 abs(절댓값)함수를 사용하였다

그 외의 부분에서는 chess판 초기화, cnt변수 초기화 등과 같은 기본 단계이므로 설명은 생략하겠다

그리고 python으로 제출하면 시간초과가 발생하므로 pypy3로 제출해야 맞았습니다!를 확인할 수 있다