[백준] [Python] ♟️ N-Queen 9663번

💡 문제 설명

백준 N-Queen

문제는 이해하기 정말 쉽다. 그리고 백트래킹을 이용해야 한다.

기본적으로 백트래킹에 대한 지식이 없다면 백트래킹을 공부한 후 읽기를 권장한다.

💡 실패한 풀이법 - 2차원 배열

2차원 배열을 사용해 놓을때마다 가로, 대각선 두개에 해당하는 칸 모두 지워봤다.

이건 아무리 시간 제한이 10초라도, 하나 대입할때마다 이중for문,

들어갈수 있는지 체크할때마다 이중for문을 사용하기 때문에

당연히 시간 초과가 발생한다.

💡 느린 풀이법 - (Python은 시간초과)

이 풀이법은 무조건 맞다고 생각했지만, pypy3 으로 제출시 통과, python으로 제출시 시간초과가 발생한다.

이유는 q_check인 들어갈 수 있는지 체크하는 과정에서 for문이 사용되기 때문이다.

이 풀이법은 가능한 갯수만 출력하는게 아니라 그때 어떻게 놓아야 하는지 찾아야 할때 유용하다.

23번째 줄에 주석처리한 것을 주석해제하면, 성공했을때의 각 row의 인덱스들을 출력해준다.

def q_check(x):
    # 이미 기록된 0 ~ x-1 범위 보기
    for i in range(x):
        # row (가로)체크
        # 체크하려는 row == 기록된 row(q_list[i]) 일때 False
        if row[x] == row[i]:
            return False
        # 대각선 체크
        # 체크하려는 row와 이미 기록된 row의 차가
        # 체크하려는 단계(column) 과 기록된 단계(column)의 차가 같다면 대각선이니 False
        if abs(row[x]-row[i]) == x-i: # abs() = 절댓값 함수
            return False
    # 두 경우 다 피해가면 True
    return True


def n_queen(n):
    global cnt

    # 끝까지 완성한 경우
    if n==N:
        cnt+=1
        # print(row) 를 넣으면 성공했을때 어떻게 놓았는지도 찾을 수 있다!!
        return

    for i in range(N):
      	# n번째 단계에 i번째 열에 놓아보기
        row[n] = i
        if q_check(n):
            n_queen(n+1)

N = int(input())
row = [0]*N
cnt = 0
n_queen(0)
print(cnt)

💡 가장 빠른 풀이법

이 풀이는 조금 이해하기 힘들 수 있다.

for문이 하나밖에 안보이는데, 이는 대각선을 체크할때 for문을 사용하지 않고,

대각선을 대표하는 값을 하나로 지정했기 때문이다.

또한, array에 숫자를 넣지 않고, Boolean을 사용한 array를 3개 만들었다.

N = int(input())
cnt = 0
row = [True]*N # 가로
x1 = [True]*(2*N) # 제일 왼쪽이 인덱스인 우상향 대각선
x2 = [True]*(2*N) # 제일 오른쪽이 인덱스인 우하향 대각선

def backtracking(n):
    global cnt
    # 다 도달했을 때 1카운트 후 종료
    if n==N:
        cnt+=1
        return

    for i in range(N):
        # 놓을 수 있으면
        if row[i] and x1[i+n] and x2[i+((N-1)-n)]:
            row[i]=False # 가로줄 제거
            x1[i+n]=False # 오른쪽 위 방향 대각선 제거
            x2[i+((N-1)-n)]=False # 오른쪽 아래 방향 대각선 제거

            # 자식 노드로 이동
            backtracking(n+1)

            # 백트래킹
            row[i]=True
            x1[i+n]=True
            x2[i+((N-1)-n)]=True

backtracking(0)
print(cnt)

❗row[] : 가로 줄

row는 간단하게 가로에 겹치는게 있으면 안되므로, 해당 row를 사용했으면 False로 바꿔주기만 하면 된다.

❗x2[] : 우하향 대각선

x2는 오른쪽 아래로 가는 대각선을 뜻하고, 총 2*N 개가 나올 수 있다.

각 대각선들은 가장 오른쪽에 갔을때 index를 기준으로 삼았다.

그림은 0, 1 단계를 마치고 2단계의 for문에서 i=3일때 우하향 대각선이 겹치지 않는지를 보는 것이다.

그렇다면 n 단계의 for문의 i번째 row일때 생기는 우하향 대각선은 맨 오른쪽으로 가면

i + (마지막 단계 - 지금 단계) 가 된다.

그러므로 놓았을때는

x2[i+((N-1)-n)] = False 로 바꿔주어 대각선이 사용되었음을 나타내면 된다.

들어갈 수 있는지 체크할때는

x2[i+((N-1)-n)] 가 True면 겹치지 않고, False면 겹쳐서 불가능 한것이다.

❗x1[] : 우상향 대각선

x2를 이해했다면 x1은 자동으로 이해된다.

차이점은 x2는 가장 오른쪽이 기준이었다면, x1은 가장 왼쪽이 기준이다.

그렇다면 n 단계의 for문의 i번째 row일때 생기는 우상향 대각선은 맨 왼쪽으로 가면

i + (지금 단계) 가 된다.

그러므로 놓았을때는

x1[i+n] = False 로 바꿔주어 대각선이 사용되었음을 나타내면 된다.

들어갈 수 있는지 체크할때는

x1[i+n] 가 True면 겹치지 않고, False면 겹쳐서 불가능 한것이다.

💡 마무리

N-Queen 문제 중 가장 레이팅이 낮은 쉬운 문제였지만 쉽지 않았다.

다음 포스팅은 🧩 N-Queen (Easy) 를 풀어보겠다.