[Level 3] N-Queen

programmers.co.kr/learn/courses/30/lessons/12952?language=python3

코딩테스트 연습 - N-Queen

---

접근

어떤 (x, y)에 퀸을 놓는다면 같은 x축과 y축 그리고 (x, y)에 대각선에 퀸을 놓을 수 없다.

위의 조건으로 NxN의 칸에 N개의 퀸을 놓아야한다.

 

만약 어떠한 행에 퀸을 놓는다면 더이상 그 행에는 퀸을 놓을 수 없다. 즉 각 행에는 하나의 퀸만 있을 수 있으며, 각 열에는 하나의 퀸만 놓을 수 있다. 이를 토대로 체스맵을 생성할 때 1차원 배열에 생성할 수 있을 것이다.

CHESS_MAP에 0으로 초기화된 길이 4인 1차원 리스트가 존재한다고 하자. 그렇다면 인덱스는 0, 1, 2, 3이 될 것이다.

만약 인덱스 0에 2가 들어간다면 0행 2열에 퀸을 놓았다는 표시가 된다. 그리고 더이상 0행과 2열에는 퀸을 놓을 수 없다.

 

위의 원리를 바탕으로 퀸이 표시되어있는 1차원 리스트인 CHESS_MAP과 각 열에 퀸이 있는지 알아보는 COLUMN을 만든다. COLUMN은 해당 열에 퀸이 있다면 1, 없다면 0으로 하여 빠르게 탐색을 할 수 있도록 한다.

 

이제 대각선을 검사해야한다.

백트래킹으로 각 행마다 퀸을 놓을 열을 찾아서 진행하기 때문에 이전 행에서 대각선이 위치한 열에 퀸이 있는지 검사를 하면된다. 이를 위해서 행의 차이와 열의 차이를 활용한다.

아래 맵에서 2행 1열에 퀸을 놓았다고 해보자. 그렇다면 빨간색으로 표시한 좌표에는 퀸을 놓을 수 없다.

각각 행과 열의 차이를 보면 같다는 것을 확인할 수 있다.

그리고 위에서 CHESS_MAP에는 각 인덱스는 행이되고 인덱스의 값은 퀸이 놓인 열을 의미한다.

따라서 현재 행 이전을 검사하여 0행부터 검사를 해보자. 행의 차이는 2-0 = 2가 된다. 

그리고 0행 3열에 퀸이 있다고 가정하면 열의 차이는 1열 - CHESS_MAP[0] = 1 - 3 = - 2가되는 것을 확인할 수 있다. 열의 차이를 절댓값으로 변경하면 행과 열의 차이가 같아지게되고 (2, 1)에는 퀸을 놓을 수 없게된다.

0, 0	0, 1	0, 2	0, 3
1, 0	1, 1	1, 2	1, 3
2, 0	2, 1	2, 2	2, 3
3, 0	3, 1	3, 2	3, 3

이처럼 현재 퀸이 놓인 상황에서 놓을 수 있는 곳을 찾아 N개의 퀸을 놓아보자.

 

구현

dfs함수에 0으로 초기화된 n길이의 리스트 2개를 전달한다. 두 개의 리스트는 체판에서 퀸을 놓은 정보를  포함한 chess_map과 해당 열에 퀸이 존재하는지 확인하는 column리스트이다. 

그리고 현재 행을 의미하는 row와 n을 전달한다.

def solution(n):
    global answer
    answer = 0
    dfs([0]*n, [0]*n, 0, n)
    return answer

 

dfs 함수에서는 현재 행의 위치인 row가 n이라면 n개의 퀸을 놓았다는 의미이기 때문에 최종해를 증가시킨다.

n이 아닐 때에는 퀸을 놓을 열을 찾는다. 

만약 column에서 해당 col위치에 퀸이 있다면 다음으로 넘어가며

대각선에 퀸이 있는지 판별하여 없다면 해당 col에 퀸을 놓았다는 의미로 1을, chess_map[행] = col(열)을 놓도록 한다.

그리고 재귀호출을 통해 현재까지의 정보와 row를 1증가시켜 전달하도록 한다.

def dfs(chess_map, column, row, n):
    if row == n:
        global answer
        answer += 1
        return
    
    for col in range(n):
        if column[col]:
            continue
        if check_diag(chess_map, row, col):
            column[col] = 1
            chess_map[row] = col
            dfs(chess_map, column, row+1, n)
            column[col] = 0
            chess_map[row] = 0

 

이후 대각선을 검사한다.

위에서 설명한 것처럼 현재 행을 기준으로 이전 행들을 검사하여 행과 열의 차이를 검사하여 차이가 같다면 False, 다르다면 True를 반환한다.

def check_diag(row, col):
    for i in range(row):
        if row - i == abs(col - chess_map[i]):
            return False
    return True

---

전체 코드

def check_diag(chess_map, row, col):
    for i in range(row):
        if row-i == abs(col-chess_map[i]):
            return False
    return True

def dfs(chess_map, column, row, n):
    if row == n:
        global answer
        answer += 1
        return
    
    for col in range(n):
        if column[col]:
            continue
        if check_diag(chess_map, row, col):
            column[col] = 1
            chess_map[row] = col
            dfs(chess_map, column, row+1, n)
            column[col] = 0
            chess_map[row] = 0
        

def solution(n):
    global answer
    answer = 0
    dfs([0]*n, [0]*n, 0, n)
    return answer