TIL #26 : 백 트랙킹 기법

📝 백 트랙킹

💡 제약 조건 만족 문제에서 해를 찾기 위한 전략!

• 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크
• 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack!
  ➜ 바로 다른 후보군으로 넘어가며 최적의 해를 찾는 방식

• 고려할 수 있는 모든 경우의 수를 상태 공간 트리로 표현
• 각 후보군을 DFS 방식으로 탐색하면서 조건에 부합하는지 체크!

🚩 N Queen 문제

👏 대표적인 백트래킹 문제로,
n x n 크기의 체스판에 n개의 퀸을 서로 공격할 수 없도록 배치하는 문제
❗ 퀸: 수직, 수평, 대각선으로 공격 가능!

◾ 퀸 수평 이동 가능 ➜ 하나의 행, 하나의 퀸
◾ 퀸 수직 이동 가능 ➜ 하나의 열, 하나의 퀸
👉 현재 위치에서 수직과 대각선에 대해서만 확인하면 됨 :D

def DFS(N,current_row, current_candidate, result):
    if current_row == N:
        result.append(current_candidate[:])
        # 슬라이싱을 통해서 값을 할당하면 새로운 id가 부여되며, 서로 영향을 받지 않는다.
        return

    for candidate_col in range(N):
        if is_available(current_candidate, candidate_col):
            current_candidate.append(candidate_col)
            DFS(N, current_row+1, current_candidate, result)
            current_candidate.pop()

def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):
        if candidate[queen_row] == current_col or abs(candidate[queen_row]-current_col) == abs(queen_row-current_row):
            return False
    return True


def solve_n_queens(N):
    result = []
    DFS(N, 0, [], result)

    return result

• is_vailable()
  • candidate[queen_row] == current_col : 수직 체크
  • abs(candidate[queen_row]-current_col) == abs(queen_row-current_row) : 대각선 체크