백준_9663_N-Queen(백트래킹)

def check(deph, i):
    global n
    flag = False
    if deph == 0:
        return not flag
    if i == 0:
        if chess[deph-1][i+1] == 0:
            flag = True
    elif i == n-1:
        if chess[deph-1][i-1] == 0:
            flag = True
    else:
        if chess[deph-1][i-1] == 0 and chess[deph-1][i+1] == 0:
            flag = True
    return flag

def dfs(n, deph, cnt):
    global result
    if deph == n:
        if cnt == n:
            print(chess)
            result += 1
        return
    for i in range(n):
        if not visited[i]:
            if check(deph, i):
                visited[i] = True
                chess[deph][i] = 1
                dfs(n, deph+1, cnt+1)
                chess[deph][i]= 0
                visited[i] = False

n = int(input())
chess = [[0]*n for _ in range(n)]

result = 0
visited = [False] * n
dfs(n, 0, 0)
print(result)

처음 푼 방식 -> 메모리도 비 효율적일 뿐더라 답도 틀렸다.

def check_position(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(x):
    global result
    if x == n:
        print(row)
        result += 1
    else:
        for i in range(n):
            row[x] = i
            if check_position(x):
                dfs(x+1)

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

그래도 문제를 해결하려고 노력하면서 백트래킹에대해 많이 익숙해졌다. 예전에 풀때는 백트래킹 과정이 머리에 그려지진 않았는데 이번에는 머리 속으로 백트래킹이 어떻게 수행되는지 고민하면서 문제를 풀었다.