[백준 9663번] N-Queen

9663번: N-Queen

이번 문제는 크기가 N x N 체스판 위에 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제이다.

 

본인은 체스를 좋아하지 않아서 룰을 잘 몰랐는데, 퀸은 상하좌우와 대각선에 있는 말을 공격할 수 있기 때문에 모든 말은 서로 상하좌우와 대각선에 배치할 수 없다.

 

일단 이 문제는 모든 경우의 수를 구하기 위해서 완전 탐색 기법 중 하나인 DFS를 사용하게 되면 14^14(1 <= N < 15)의 경우의 수가 나오게 되어 제한시간 내에 풀이를 할 수 없다.

 

따라서 백트래킹 알고리즘을 사용하여 다른 퀸으로 인해 자리를 배치하지 못하는 경우의 수는 사전에 차단해야 한다.

 

이 문제를 풀이하는 핵심은 '다른 퀸으로 인해 자리를 배치할 수 있는지 없는지 판단하는 조건'을 구하는 것이다.

 

같은 열에는 퀸을 2개이상 배치할 수 없기 때문에 해당 열에 배치했는지 여부를 저장하는 1차원 리스트를 선언하면 되는데, 대각선에 다른 퀸이 존재하는지 확인하는 함수를 만드는 것이 조금 까다로웠다.

 

# python3 시간초과 코드
def can_move(x,y):

    for i in range(4):
        temp_x, temp_y = x,y
        while 0 <= temp_x < n and 0 <= temp_y < n:
            if area[temp_x][temp_y] == 1:
                return False
            temp_x += dx[i]
            temp_y += dy[i]

    return True

def dfs(row):

    global answer

    if row >= n:
        answer += 1
        return
    
    for i in range(n):
        if not used_col[i] and can_move(row,i):
            area[row][i] = 1
            used_col[i] = True
            dfs(row+1)
            area[row][i] = 0
            used_col[i] = False

dfs(0)
print(answer)

처음에는 해당 좌표에서 대각선에 있는 좌표를 일일이 방문하는 방식으로 구현했는데, pypy3로는 통과되었지만 python3 에서는 시간초과가 발생하였다.

 

따라서 조금 더 효율적으로 대각선 사용가능 여부를 확인하는 방법을 찾아야했고, 바킹독 알고리즘의 강의를 참고하여 1차원 리스트(used_1, used_2, used_3)에 각 대각선 정보를 저장하여 문제를 풀이하였다.

 

배운 점 및 느낀 점

1. 완전 탐색으로 모든 경우의 수를 구하기에 시간이 오래 걸리는 경우, 백트래킹을 사용하여 시간복잡도를 줄일 수 있다.
2. 고정된 범위를 가진 값들은 미리 1차원이나 2차원 리스트를 선언하여 반복된 연산과 시간복잡도를 줄일 수 있다.(방문여부)