백준 9663번 : N-Queen (by python) - DFS(백트래킹)

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

 

해당 풀이는 Python 으로 제출시에도 시간초과가 발생하지 않습니다.

 

초기 아이디어

처음에 문제를 풀 때는 2차원 배열을 사용하여 체스판을 표현한 후, 백트래킹을 이용해 각 칸에 퀸을 배치했다. 결과는 당연히 시간초과가 발생했다.

N이 커질수록 백트래킹을 통해 모든 가능성을 탐색하는 과정에서 시간 복잡도가 급격히 증가하기 때문이다.

 

이를 해결하기 위해서 퀸의 이동 방식에 대해서 다시 생각해보면 아래와 같다.

 

퀸의  이동방식

 

https://opentutorials.org/module/3806/22853

퀸은 다음과 같은 방식으로 이동한다.

 

• 같은 행에 있는 퀸끼리는 서로 공격할 수 없으므로, 한 행에 하나의 퀸만 배치할 수 있다.
• 퀸은 같은 열에 있는 다른 퀸과도 공격할 수 없으므로, 한 열에도 퀸은 하나만 배치되어야 한다.
• 대각선 상에 있는 퀸은 서로 공격할 수 있으므로, 대각선에 대한 체크도 필요하다.

 

이를 통해 체스판을 2차원 배열로 나타낼 필요가 없으며, 각 행마다 퀸을 어디에 배치할지 기록하는 1차원 배열을 사용하는 것으로 충분하다.

 

초기 해결 풀이 (시간초과)

def is_avaliable(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(start):
    global result
    if start == n:
        result += 1
        return
    else:
        for i in range(n):
            row[start] = i
            if is_avaliable(start):
                dfs(start + 1)

n = int(input())
result = 0
row = [0] * n
dfs(0)
print(result)

 

퀸을 배치하는 자리마다 다른 퀸과의 공격 가능성을 모두 확인하며 배치하도록 해결한 코드이다.

각 행다마 퀸을 배치하며 is_available 함수를 통해 현재 위치에 퀸을 놓을 수 있는지를 확인하기 때문에 시간 복잡도가 O(N!)으로 시간초과가 마찬가지로 발생했다.

 

최적화 아이디어

시간 초과 문제를 해결하기 위해 각 대각선을 관리하는 별도의 배열을 도입했다.

 

• diag1[] 배열: 부대각선(↙)에서 퀸이 배치되었는지 여부를 추적
• diag2[] 배열: 주대각선(↘)에서 퀸이 배치되었는지 여부를 추적

** NxN 체스판에서 대각선의 개수는 다음과 같이 구할 수 있다.

대각선 개수 : (n*2 -1)개

 

 

 

각 대각선의 특징을 살펴보면 대각선배열을 1차원으로 사용할 수 있다.

부대각선(↙)

• 부대각선의 경우 동일한 대각선위의 모든 좌표들은 동일한 row+col 값을 가진다.
• 해당 값은 0 ~ (대각선의 개수-1) 까지 존재한다.

dig1[row+col] = True 
dig1[row+col] = False

부 대각선의 row+col 값을 사용해 해당 대각선에 배치할 수 있는지 없는지 위 코드와 같이 설정할 수 있다.

새로 퀸을 놓을 좌표 값의 row+col 에 대해 해당 dig1 배열 인덱스 값을 확인하면 상수시간에 여부를 체크할 수 있다.

 

주대각선(↘) 

 

• 주대각선의 경우 동일한 대각선위의 모든 좌표가 같은 row-col 값을 가진다.
• 이때 음수 값이 존재하는데 배열의 인덱스에 그대로 대입해주기 위해  (+n -1) 을 하면 해당 값은 0 ~ (대각선의 개수-1) 까지 존재하게 된다.

dig2[row-col +n -1] = True
dig2[row-col +n -1] = False

 

주대각선 좌표의 row-col+n-1 값을 사용해 해당 대각선에 배치할 수 있는지 없는지 위 코드와 같이 설정할 수 있다.

새로 퀸을 놓을 좌표 값의 row-col+n-1 에 대해 해당 dig2 배열 인덱스 값을 확인하면 상수시간에 여부를 확인할 수 있다.

 

퀸이 이동할수 있는 방향에대해 한번씩만 체크해도 해당 자리에 퀸을 놓을 수 있는지 여부를 체크할 수 있다.

• not cols[col]: 현재 열에 이미 다른 퀸이 배치되어 있는지 확인
• not diag1[row + col]: 현재 퀸을 배치하려는 위치가 부대각선(↙)에서 공격받는지 여부를 확인
• not diag2[row - col + n - 1]: 현재 퀸을 배치하려는 위치가 주대각선(↘)에서 공격받는지 여부를 확인

if not cols[col] and not diag1[row + col] and not diag2[row - col + n - 1]:

 

풀이

def dfs(row):
    global result
    
    # if row == n: 퀸을 모두 배치한 경우(즉,n번째 행까지 도달한 경우), 
    # 하나의 해답을 찾았으므로 result를 1 증가
    if row == n:
        result += 1
        return
        
    for col in range(n):
        # 열, 부대각선, 주대각선에 퀸이 없을 때만 배치
        if not cols[col] and not diag1[row + col] and not diag2[row - col + n - 1]:
        
            # 퀸을 배치하고 상태 업데이트 (해당 열, 부대각선, 주대각선에 대해 처리)
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True
            
            dfs(row + 1)
            
            # 백트래킹: 퀸 제거
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False

n = int(input())
result = 0
cols = [False] * n  # 열을 추적하는 배열
diag1 = [False] * (n * 2 - 1)  # 부대각선 (↙)
diag2 = [False] * (n * 2 - 1)  # 주대각선 (↘)
dfs(0)
print(result)