[BOJ_Python] 9663.N-Queen

문제

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

 

사용 알고리즘

백트레킹

 

풀이

1. 퀸은 상, 하, 좌, 우, 대각선을 원하는 만큼 갈 수 있다.

    여기서 '상하, 좌우, 대각선' 3가지로 나눠서 확인하였다.

2. 상하 - 한 줄에 퀸 한 개씩 놓으며 백트레킹을 진행하였다.

    좌우 - 한 열에 한 개의 퀸만 가능하기 때문에 index에 관한 딕셔너리로 관리하였다.

    대각선 - 해당 줄(i)에 매칭 되는 값을 리스트에 넣어 관리하였다.

                 대각선의 경우 일정한 비율로 증가, 감소하기 때문에

                 (한 줄 전에 것은 열의 값이  +1 또는 -1 -> 즉, x줄 전의 값은 y+x 또는 y-x)

                 x1 - x2와 절댓값 y1 - y2가 같으면 한 선상에 위치하는 점을 이용하였다.

                 이때 풀이에서 for문을 사용했는데 매번 for문을 확인하는 절차에서 시간이 걸려

                 python은 시간 초과가 나고, pypy만 통과한 것 같다.

 

3. 때문에 python으로 푼 풀이를 한참 찾던 중 맘에 드는 풀이를 발견했다.

    해당 풀이는 for문을 사용하지 않고 리스트로 관리하여 시간을 절약하였다.

    해당 풀이를 자세히 살펴보면 N * N에서 나올 수 있는 대각선의 갯수는 한 방향마다 2N-1개이다.

    방향은 2개 (\, /) 가 존재하므로 따로 리스트로 관리하였다.

    하나의 직선은 같은 비율로 증감하기 때문에 row + col과 row - col + N으로 관리가 가능하였다.

    (이때, row < col의 경우를 고려해야하기 떄문에 N을 더해서 관리하였다.)

    for문을 사용하지 않고 해당 직선이 사용되었는지 리스트 인덱스로 바로 찾기 때문에 시간이 훨씬 절약된 것을 확인할 수 있었다.

    

코드 

내가 푼 코드

import sys

input = sys.stdin.readline

# 상하 -> 백트래킹으로 관리
# 좌우 -> index를 리스트로 관리
# 대각선 -> x1 - x2 != abs(y1 - y2)로 관리


def check_diagonal(c_level):
    # 대각선 확인
    for p_level in range(c_level):
        if c_level - p_level == abs(visited_i[p_level] - visited_i[c_level]):
            return False
    return True


def backtracking(level):
    global cnt

    # 마지막 행을 지나갔다면 횟수 증가 후 마침
    if level == N:
        cnt += 1
        return

    # 아직 진행 중이라면 col을 돌며 둘 수 있는 위치 확인
    for j in range(N):
        # 해당 인덱스를 쓴 적이 있는지 확인
        if visited_d[j] == -1:
            visited_d[j] = level
            visited_i[level] = j

            if check_diagonal(level):
                backtracking(level + 1)

            visited_d[j] = -1
            visited_i[level] = -1


N = int(input())

cnt = 0
visited_i = [-1] * N
visited_d = {_: -1 for _ in range(N)}

backtracking(0)
print(cnt)

 

다른 사람이 푼 코드

def Queen(row):
    global count, board
    if row == N:
        count += 1
        return

    for col in range(N):
        if cols[col] and diagonal_1[row + col] and diagonal_2[row - col + N]:
            cols[col] = False
            diagonal_1[row + col] = False
            diagonal_2[row - col + N] = False       

            Queen(row + 1)

            cols[col] = True
            diagonal_1[row + col] = True
            diagonal_2[row - col + N] = True

N = int(input())
count = 0
cols = [True for _ in range(N)]
diagonal_1 = [True] * 2*N
diagonal_2 = [True] * 2*N

Queen(0)
print(count)

결과

내가 작성한 코드

 

다른사람이 푼 코드