[BOJ 9663] N-Queen(Python)

문제

N-Queen

---

문제 해설

백트래킹에 관한 대표적인 문제이다.

• 퀸은 각 줄 마다 반드시 하나씩 들어가야 한다.
• 퀸이 있는 자리에 대각선, 세로선에는 다른 퀸이 존재할 수 없다.

처음엔 퀸들의 위치가 저장되있는 리스트를 만들어 x,y 좌표를 저장했는데 시간초과가 나면서 생각을 해봤지만, 답이 나오지 않아 찾아봤다. 퀸의 좌표를 일일이 확인하면서 확인하는 방식이 아닌, 일자 배열을 활용하여 문제를 푸는 방식이 대다수 였다.

사진출처 : https://rebas.kr/761

---

시간초과 코드

n = int(input())
queen = []
answer = 0


def possible(x, y):
    for nx, ny in queen:
        # 직선의 경우
        if y == ny:
            return False
        # 왼쪽 대각선의 경우
        if x - nx == y - ny:
            return False
        if x - nx == ny - y:
            return False
    return True


def find(depth):
    global answer
    if depth == n:
        answer += 1
        return
    for y in range(n):
        # 다른 queen의 위치를 확인하고 가능한지 확인
        if possible(depth, y):
            queen.append((depth, y))
            find(depth + 1)
            queen.pop()


for i in range(n):
    # 첫 줄의 퀸의 위치만 옮겨줌.
    # 각 줄에는 하나의 퀸만 올 수 있음.
    queen.append((0, i))
    find(1)
    queen.pop()
print(answer)

풀이 코드

n = int(input())
queen = []
a, b, c = [True] * n, [True] * (2 * n - 1), [True] * (2 * n - 1)
answer = 0


def find(x):
    global answer
    if x == n:
        answer += 1
        return
    for y in range(n):
        # 해당 자리에 퀸이 올수 있다면
        if a[y] and b[x + y] and c[x - y + n - 1]:
            a[y] = b[x + y] = c[x - y + n - 1] = False
            find(x + 1)
            a[y] = b[x + y] = c[x - y + n - 1] = True


for i in range(n):
    # 첫 줄의 퀸의 위치만 옮겨줌.
    # 각 줄에는 하나의 퀸만 올 수 있음.
    a[i] = b[i] = c[n - 1 - i] = False
    find(1)
    a[i] = b[i] = c[n - 1 - i] = True
print(answer)