9663. N-Queen

TLDR#

브루트포스 문제이긴 하나, 대각선으로도 생각해 볼 필요가 있는 문제. i, j에 퀸을 배치했다면 앞으로는 절대 i 열 OR j 행에 퀸이 배치될 일은 없을 것이다. 그런데 퀸은 대각선으로도 움직일 수 있으니 각 대각선 axis에 퀸이 배치될 일이 없게끔 만드는 것이 핵심이다.

Snippet#

def se(i, j, n) -> int:  
    """  
    (i, j)는 se 세상의 몇번째 좌표에 투영되나요?

    ```
    3 4 5 6
    2 3 4 5
    1 2 3 4
    0 1 2 3
    ```

    위의 예시를 그대로 들고 와서 보면, se 세상의 unit vector를 구할 수 있습니다.
    se 세상은 2D 세상이 압축되어 1D로 표현되므로 2 by 1 차원의 행렬이 되며,
    값이 우상향을 향하여 증가하는 것으로 보아 벡터는 [-1, 1]t 가 될 수 있음을
    알 수 있습니다.

    따라서 우리 세상의 (i,j) 좌표는 se 세상에서 [i, j] * [-1, 1]t = -i + j로 투영
    될 것입니다.

    아직 안 끝났습니다. 왜냐하면 벡터는 방향만을 나타내지, 시프트를 지원하지 않기
    때문이죠. se 세상의 0은 우리 세상에서 n-1 만큼 뒤쳐져 있기 때문에, n-1 만큼을
    더해주어야 합니다. 무슨 말이냐면, 우리 세상에서 (0, 0)은 se 세상에서 (3)이
    됩니다.

    따라서, se(i, j) => -i + j + (n - 1)
    """
    return -i + j + (n - 1)


def ne(i, j, n) -> int:  
    """  
    (i, j)는 ne 세상의 몇번째 좌표에 투영되나요?

    ```
    0 1 2 3
    1 2 3 4
    2 3 4 5
    3 4 5 6
    ```

    위의 예시를 통해 보면 ne 세상의 unit vector를 구할 수 있습니다.
    ne 세상의 unit vector는 [1, 1]t 입니다.

    따라서 우리 세상의 (i, j) 좌표는 ne 세상에서 [i, j] * [1, 1]t = i + j
    로 투영될 것입니다.

    시프트가 필요한가요? 아닙니다. (0, 0)은 ne 세상에서 0입니다.

    따라서, ne(i, j) => i + j
    """
    return i + j


def recurse(  
    n: int,  
    col: int,  
    row_visited: list[bool],  
    ne_visited: list[bool],  
    se_visited: list[bool],  
) -> int:  
    if col == n:  
        return 1

    cnt = 0

    for row in range(n):
        if row_visited[row] or ne_visited[ne(row, col, n)] or se_visited[se(row, col, n)]:
            continue

        # visit 처리
        row_visited[row] = True
        ne_visited[ne(row, col, n)] = True
        se_visited[se(row, col, n)] = True

        # Do visit
        cnt += recurse(n, col + 1, row_visited, ne_visited, se_visited)

        # visit 무효
        row_visited[row] = False
        ne_visited[ne(row, col, n)] = False
        se_visited[se(row, col, n)] = False

    return cnt



def main(n: int) -> int:  
    n_diag = n * 2 - 1  
    row_visited = [False for _ in range(n)]  
    ne_visited = [False for _ in range(n_diag)]  
    se_visited = [False for _ in range(n_diag)]

    return recurse(n, 0, row_visited, ne_visited, se_visited)


if __name__ == "__main__":  
    n = int(input())  
    print(main(n))

Sample Input & Expected Output#

Input#

Expected Output#

Notes#

row_visited: 말 그대로 해당 행을 방문했는지 체크
ne_visited: nxn 테이블을 우상향 방향으로 잘랐을 때 해당 라인을 방문했는지 체크
se_visited: nxn 테이블을 우하향 방향으로 잘랐을 때 해당 라인을 방문했는지 체크

예를 들어 n = 4일 경우, 대각선은 n*2-2=7 개이다.

ne_visited

se_visited