3-3. [그래프 탐색] 백트래킹

1. N Queen 문제

 

 

 

 

def check(a, row, col):
    for r, c in enumerate(a):
        if col == c or abs(col - c) == abs(row - r):
            return False
    return True


def recursive(row, a):
    global result

    if row == 4:
        result.append(a[:])
        return

    for col in [0, 1, 2, 3]:
        if check(a, row, col):  # 가지치기 (이전 퀀의 위치에 따라 탐색 제외)
            a.append(col)
            recursive(row + 1, a)
            a.pop()


result = []
recursive(0, [])
print(result)  # [[1, 3, 0, 2], [2, 0, 3, 1]]

 

(참조) 위와 동일한 로직이지만, append, pop 사용하지 않도록 변경해봄

 

def check(a, row, col):
    for r, c in enumerate(a[:row]):
        if col == c or abs(col - c) == abs(row - r):
            return False
    return True


def recursive(row):
    global result

    if row == 4:
        result.append(a[:])
        return

    for col in [0, 1, 2, 3]:
        a[row] = col
        if check(a, row, col):  # 가지치기 (이전 퀀의 위치에 따라 탐색 제외)
            recursive(row + 1)


a = [0] * 4
result = []
recursive(0)
print(result)  # [[1, 3, 0, 2], [2, 0, 3, 1]]