💡 풀이 전략

백트래킹 기법을 사용했다. 1행 1열부터 퀸을 배치하고 2행으로 넘어가 1열부터 퀸을 배치하고 퀸을 배치할 수 있는 조건이면 다음 행으로 넘어가고 배치할 수 없는 조건이면 다음 열로 넘어가는 방식이다. 이런 식으로 마지막 행까지 퀸이 배치가 되면 결과값에 +1을 해주는 방식이다. 어떤 방식으로 퀸이 성공적으로 N개가 배치가 되면 N-1개 배치했던 순간으로 돌아가 다음 열에 퀸을 배치함으로써 모든 경우를 구할 수 있다.

📝 소스 코드

import sys
input = sys.stdin.readline

# 같은 줄이나 대각선 줄에 퀸이 존재하는 체크하는 함수
def check(x):
    for i in range(x):
        if board[x]==board[i]:
            return False
        elif abs(board[x]-board[i]) == x-i:
            return False
    return True

# 여기서 x는 x번째 열을 뜻함
def dfs(x):
    global result
    # 만약 x번째 열이 N과 같으면 체스판을 벗어난 것이므로 종료하고 결과값에 1을 추가
    if x==N:
        result+=1
        return
    # 그렇지 않다면
    else:
        # 0번부터 N-1번 열까지 퀸을 배치해봄
        for i in range(N):
            board[x]=i
            # 퀸을 배치해보고 조건을 만족하면 다음 줄로 넘어감
            if check(x)==True:
                dfs(x+1)

N = int(input())
# board가 1차원 배열인 이유는 board안의 인덱스는 체스판의 행을 뜻하고 board값은 인덱스 행에 퀸이 놓인 열을 뜻함
# 즉 board[2]=1이면 3번째 줄에 2번째 열에 퀸이 놓인 것임(인덱스는 0부터 시작하므로)
board = [0]*N
result = 0

dfs(0)
print(result)

🔨 이차원 배열과 시간 초과 이슈에 대해

체스판이 정사각형이므로 이차원 배열을 사용해도 되지만 필자를 포함한 대부분의 풀이는 일차원 배열을 이용한다. 이 부분이 상당히 헷갈리는 부분인데, 1차원 배열의 인덱스는 체스판의 행을, 배열의 값은 열을 나타낸다. 위에 주석에도 써져 있지만 board[2]=1이라고 가정하면 3번째 행 2번째 열에 퀸이 존재한다는 뜻이다.(인덱스는 0부터 시작하므로)
이 같은 방법을 통해 공간 복잡도와 시간 복잡도를 줄일 수 있다.

이 문제를 풀면서 시간 초과 이슈를 상당히 많이 겪었는데, 일단 C++과 Java로 같은 논리로 제출하면 시간 초과 문제가 해결된다고 한다.
파이썬의 경우 if, elif 대신 or을 사용했더니 시간초과가 발생했다.(이유는 잘 모르겠는데 if문에서 걸러지면 elif를 거치지 않아서인가..? 내가 알기로는 or도 앞부분이 false이면 뒷부분을 확인하지 않는걸로 아는데 정확한 이유를 잘 모르겠다)

def check(x):
    for i in range(x):
        if board[x]==board[i]:
            return False
        elif abs(board[x]-board[i]) == x-i:
            return False
    return True

위 코드가 통과한 코드이고

def check(x):
    for i in range(x):
        if board[x]==board[i] or abs(board[x]-board[i]) == x-i:
            return False
    return True

위 코드가 시간 초과가 발생한 코드이다.
또한 python3대신 pypy3로 제출하면 통과가 되는 코드도 있다고 한다.