[Baekjoon] 9663번 : N-Queen

9663번: N-Queen

 

문제 풀이

퀸은 자신의 위치를 기준으로 상, 하, 좌, 우, 대각선 방향으로 보드 끝까지 공격이 가능하다.

공격이 닿는 경우를 확인하여 닿으면 False를 반환하는 함수를 만든다.

1) 열이나 행이 겹치는 경우 : 같은 열에 퀸이 있는지 확인

2) 대각선에 걸친 경우 : 대각선 위치에 있다는 것은 두 퀸의 x좌표의 차와 y좌표의 차가 같은 경우 

 

보드의 한칸씩 반복문으로 확인하며 공격받지 않는 위치라면 퀸을 놓고, 아니면 패스한다. 하나씩 퀸이 놓여지고 퀸의 개수가 n 개가 되면 경우의 수(answer) 을 1추가한다.

 

코드

n = int(input())

graph = [0] * n
answer = 0

def not_attack(x):
    # 모든 열을 탐색
    for i in range(x):
        # 열이 같거나, 대각선에 퀸이 있으면 False 반환
        if graph[x] == graph[i] or abs(graph[x] - graph[i]) == abs(x - i):
            return False
    return True

def solution(queen_n):
    global answer
    # 퀸이 n개가 놓이면 경우의 수 하나 추가
    if queen_n == n:
        answer += 1

    else:
        for i in range(n):
            graph[queen_n] = i
            # 공격을 할 수 없는 위치이면
            if not_attack(queen_n):
                solution(queen_n + 1)


solution(0)
print(answer)

 

느낀점

처음엔 백트래킹 알고리즘을 모른채로 dfs로 한칸씩 공격을 할 수 있는지 없는지 확인하도록 구현했었는데 시간초과가 떴다.

왜 백트래킹을 써야하는지 왜 이런 유형에서 백트래킹이 더 효율적인지 몸소 느꼈다 ㅎ..  

백트래킹 알고리즘을 이용하고, 규칙에 따라 일반화한 식을 쓰면 훨씬 더 간단하게 구현할 수 있더라..!

그런데 여전히 시간초과가 발생한다. 파이썬으로는 시간을 맞추기가 어렵다고 하는데 어떻게 최적화를 할 수 있을지 고민해봐야겠다.