[PY] 9663 : N-Queen

 

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

결론만 적으면 내 힘으로 못 풀었다. 그래서 이렇게 별도로 글을 쓴다.
작동이 되는 방식을 두 가지 구현을 했다. 하나는 2차원 배열로, 하나는 1차원 배열로..
더 깊이 고민하면 됐을지도 모르겠지만 (정신)체력적인 한계로 책을 결국 펼치고 말았다.

분명 몇 달 전에도 비슷한 엔딩으로 모든 구조를 되새겼다고 생각하고 지나갔던 문제인데,
사람이 기억하려고 의식적으로 노력해야 하는 것 같다.

N-Queen 문제는 어쨌든 배경지식으로 체스에서 Queen이 할 수 있는 것을 알아야 한다.
퀸은 진짜 사방팔방 움직일 수 있다. 말 그대로 8 방향에서 움직일 수 있다. 상하좌우 북서 동북 남동 남서

서로 공격하지 않게 해야 한다고 하면 사전에 놓을 수 없는 범위를 설정하는 것이 좋겠는데, 이 부분에 대한 계산을 가능한한 줄여야했다.
놓을 수 없는 부분이 나올 때까지 탐색하는 것도 좋지만 영 성치 않으면 갖다 버리고 바로 다른 선택지 고려해보는 코드까지 생각을 해야 했다.

1차 실패 : 2차원 배열로 구현

원초적인 고민만 했다. 퀸이 배치되면 놓을 수 없는 구역을 모두 표시해둔다.
다음 퀸은 놓을 수 없는 구역을 피해서 배치된다. 퀸을 더 이상 놓을 수 없다고 판단된 경우 배치된 퀸의 갯수에 따라 할 일이 달라진다.

# N queen
import sys

sys.setrecursionlimit(2000)

# 퀸은 8방향 어디든 갈 수 있으니 이에 대한 처리가 필요하다.
    # 1. 퀸을 놓으려고 할 때 기존에 놓아진 모든 퀸들과의 상호 확인을 한다.
    # 2. 퀸을 생성 하는 시점에서, 판에 놓을 수 있는 여부를 업데이트 한다.

queenCnt = int(input())
# 퀸의 갯수는 실제 범위와 동일하게 한다.

array = [[0 for col in range(16)] for row in range(16)]
totalResult = 0
# 0은 놓아진 게 없음, 1은 퀸이 설치되었음, 2는 퀸을 설치 할 수 없음으로 하자.

def queenInstaller(array, _x, _y):

    if array[_x][_y] != 0:
        # 배치가 가능한지를 기본적으로 확인해야한다.
        #print("install failed! tried axis is : " + str(_x) + " , " + str(_y))
        return
    # 배치가 가능하다면 배치를 한다.
    array[_x][_y] = 1
    #print("installed in " + str(_x) + " " + str(_y))

    if(_x + 1 == queenCnt):
        # 정한 갯수만큼 설치 했다면 거기서 중단 할 수 있다.

        #print("FULL INSTALL COMPLETED!")
        #for a in range(0, 10):
            #for b in range(0, 10):
                #print(str(array[a][b]), end="")
            #print("")
        global totalResult
        totalResult += 1
        return

    # 배치 금지 구역을 새롭게 설정해야한다.
    for i in range(queenCnt):
        if(_x + i >= queenCnt) or (_y + i >= queenCnt):
            c = 0
        else:
            if(array[_x + i][_y + i] == 0):
                array[_x + i][_y + i] = 2
            #print("blocked " + str(_x + i) + " " + str(_y + i))

            # 남동
        if(_x - i <= 0) or (_y - i <= 0):
            c = 0
        else:
            if(array[_x - i][_y - i] == 0):
                array[_x - i][_y - i] = 2
            #print("blocked " + str(_x - i ) + " " + str(_y - i))

            # 북서
        # 북서쪽 남동쪽 가로지르는 대각선 처리

        tmpXplus = _x + i
        tmpYplus = _y + i
        tmpXminus = _x - i
        tmpYminus = _y - i

        if(tmpYplus >= queenCnt or tmpXminus < 0):
            c = 0
        else:
            if(array[tmpXminus][tmpYplus] == 0):
                array[tmpXminus][tmpYplus] = 2
                #print("blocked " + str(tmpXminus) + " " + str(tmpYplus))

        if(tmpXplus >= queenCnt or tmpYminus < 0):
            c = 0
        else:
            if(array[tmpXplus][tmpYminus] == 0):
                array[tmpXplus][tmpYminus] = 2
                #print("blocked " + str(tmpXplus) + " " + str(tmpYminus))


            # 북동쪽과 남서쪽 가로지르는 대각선 처리

        if(array[_x][i] == 0):
           array[_x][i] = 2

        if(array[i][_y] == 0):
            array[i][_y] = 2


    for j in range(0, queenCnt):
        local_array = [row[:] for row in array]
        queenInstaller(local_array, _x + 1, j)
        # _x 기반으로 움직이게끔 한다. 즉 다음 작동은 
        # 기존 _x 다음줄로 항상 진행되고, _y 가 순차적으로 움직이며 배치를 시도한다.
        # 그럼 결과적으로 _x가 놓는데 성공한 갯수가 된다. 결국 같은 열에선 이뤄 질 수 없으니까
        # 다만 이 설치가 성공한 시점에서 갯수를 세어보고 맞다면 거기서 해당 과정을 중단 할 수 있다.


for i in range(0, queenCnt):
   # print("starting install from " + str(0) + " " + str(i))
    local_array = [row[:] for row in array]
    queenInstaller(local_array, 0, i)

print(totalResult)

다 좋다. 근데 시간을 더 아껴야 했다.
그래서 1차원 배열로 전환하면 시간 상의 이득이 있을 것이라 생각했고 idx와 contents를 하나하나 헷갈려해 나가면서 결국 전환은 했다.

# 퀸은 8방향 어디든 갈 수 있으니 이에 대한 처리가 필요하다.
    # 1. 퀸을 놓으려고 할 때 기존에 놓아진 모든 퀸들과의 상호 확인을 한다.
    # 2. 퀸을 생성 하는 시점에서, 판에 놓을 수 있는 여부를 업데이트 한다.

queenCnt = int(input())
# 퀸의 갯수는 실제 범위와 동일하게 한다.

newArray = [-1] * 16
totalResult = 0

def queenInstaller(arr, idx, installedLoc):
        # 설치 한 적 없는 곳을 보자. 배치가 가능한지를 확인해야한다.
    for i in range(idx):
        if installedLoc == arr[i]:
            return
            # 기존의 설치한거랑 열이 같은지 확인한다.

        if abs(i + arr[i]) == abs(idx + installedLoc):
            return
            # 기존 설치 된 아이템 중 10시 - 5시 방향 대각선을 확인해야한다.

        if (i - arr[i]) == (idx - installedLoc):
            return
            # 기존 설치 된 아이템 중 2시- 8시 방향 대각선을 확인해야한다.

    arr[idx] = installedLoc

    if(idx + 1 == queenCnt):
        global totalResult
        totalResult += 1
        return


    for j in range(0, queenCnt):
        queenInstaller(arr, idx + 1, j)
        # _x 기반으로 움직이게끔 한다. 즉 다음 작동은 
        # 기존 _x 다음줄로 항상 진행되고, _y 가 순차적으로 움직이며 배치를 시도한다.
        # 그럼 결과적으로 _x가 놓는데 성공한 갯수가 된다. 결국 같은 열에선 이뤄 질 수 없으니까
        # 다만 이 설치가 성공한 시점에서 갯수를 세어보고 맞다면 거기서 해당 과정을 중단 할 수 있다.
    arr[idx] = -1

for i in range(0, queenCnt):
   # print("starting install from " + str(0) + " " + str(i))
    queenInstaller(newArray, 0, i)

print(totalResult)

아마 여기서 많이 기운이 나갔다. 그래서 책을 결국에 펴보니 배치에 대한 공격 범위 처리가 좀 더 요약된 상태로 처리 되는 내용이 있었다.
8 방향에 대해 확인한다는 것 중 안해도 되는 내용이 있다. 

• 행과 열은 만드는 의도에 따라 다르지만 한 쪽을 기준으로 잡고 진행하면 나머지 한 쪽만 보면된다. 심지어 숫자 기존에 등록된 행(또는 열)의 번호만 갖고 있어도 이게 놓을 수 있는 것인지 아닌지를 알 수 있다.
• 북동쪽과 남서쪽은 일반 좌표계에서 생각하면 y = x + c 인 단순 대각선 구도이다. 이전의 구현은 배치된 내용 기준으로 위 아래를 각기 구분해서 시도했지만 주어진 y x c를 이러쿵 저러쿵 하면 flag로 뒷 마무리를 할 수 있다. 정확하게는 num + i 이다.
• 북서쪽과 남동쪽은 다소 고민이 필요하다. 여기는 x와 y가 반비례한다. 그렇다는건 음수가 될 수 있는 여지도 생각해야한다. 그래서 일정한 값으로 queen의 갯수를 더 해주게 된다. queen의 갯수는 필드의 넓이이기도 해서 이 부분에 대해서 충분한 수치 교정을 도와 줄 수있다. 따라서 num - 1 + queenCnt - 1을 해주는 것이다. (queenCnt - 1)은 갯수를 idx화 하는 과정에서 발생하는 오차 교정이다.

결과적으론 이걸로 통과하기로 했다.

queenCnt = int(input())
# 퀸의 갯수는 실제 범위와 동일하게 한다.

pos = [0] * 15
flag_line = [False] * 50
flag_5_10 = [False] * 50
flag_2_8 = [False] * 50

totalResult = 0


def installQueen(num):
    for i in range(queenCnt):
        if(not flag_line[i] and not flag_2_8[i + num] and not flag_5_10[num - i + queenCnt - 1]):
            pos[num] = i
            if(num == queenCnt - 1):
                global totalResult
                totalResult += 1
            else:
                flag_line[i] = flag_2_8[i + num] = flag_5_10[num - i + queenCnt - 1] = True
                installQueen(num + 1)
                flag_line[i] = flag_2_8[i + num] = flag_5_10[num - i + queenCnt - 1] = False


installQueen(0)
print(totalResult)