[swea] 2806번: N-Queen - 파이썬(python)

백트래킹에 대한 문제를 거의 풀어보지 않아서, N-Queen 문제도 처음 접해보았다.

BFS 와 대체로 비슷하지만, 더 이상 탐색할 필요가 없는걸 쳐내는 행위를 백트래킹 이라고 한다.

따라서, 한 행씩 퀸을 놓아보는데, 지금까지 같은열 or 대각선에 퀸이 있지 않다면 계속해서 BFS 를 진행하는 것이다.

이때, 한 행씩 퀸을 순서대로 놓기 때문에, 같은 행에 여러 퀸이 놓이는 경우는 고려하지 않아도 된다.

row 리스트의 경우, 각 인덱스가 행번호를 의미하고, 각 인덱스값은 열번호를 의미한다.

즉, row의 i번째 행에 있는 값이 j라면, 퀸이 (i,j) 에 위치함을 뜻한다.

또한, visited 리스트를 두어 i번째 열에 퀸이 위치하는지를 확인할 수 있다.

이로 인해, visited[col] 에 이미 퀸이 있다면, O(1) 의 시간으로 해당 열을 쳐내게 된다.

 

check(x) 에서는 지금까지 퀸을 놓았을 때 대각선에 겹치는 퀸이 있는지의 유무를 확인한다.

 

나의 풀이

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

def dfs(x):
    global cnt
    if x == n:
        cnt += 1
        return
    for col in range(n):
        if visited[col]:  # 이미 해당 열에 있는 퀸이 있다면
            continue
        row[x] = col  # x,col 에 퀸 놓기
        if check(x):  # 대각선에 퀸이 없다면
            visited[col] = True
            dfs(x + 1)
            visited[col] = False


T = int(input())
answer = []
for t in range(1, T + 1):
    n = int(input())
    row = [0] * n  # 인덱스가 행, 인덱스값이 열
    visited = [False] * n  # i번째 열을 방문했는지 여부
    cnt = 0
    dfs(0)
    answer.append(f'#{t} {cnt}')
print(*answer, sep='\n')