백준 9663 : 문제링크

  • 문제유형 :

    • 백 트레킹

  • 설명

    • DFS를 이용하여 백트래킹 알고리즘을 구현한다
    • 각 행을 차례대로 확인하면서, 각 열에 퀸을 놓는 경우를 고려한다
    • 이 때 위쪽 행을 모두 확인하며, 현재 위치에 놓을 수 있는지 확인한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def check(x):
        for i in  range(x):
            if row[x] == row[i]:
                return False
            if abs(row[x] - row[i]) == x - i:
                return False
        return True

    def dfs(x):
        global result
        if x == n:
            result += 1
        else:
            for i in range(n):
                row[x] = i
                if check(x):   
                    dfs(x+1)
        
    n = int(input())
    row = [0] * n
    result = 0
    dfs(0)
    print(result)