백트래킹(Backtracking)

💡 백트래킹(Backtracking)이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

용어 설명

• 유망함(promising) : 진행 중인 경로가 해답을 찾을 가능성이 있음을 의미
• 유망하지 않음(non-promising) : 진행 중인 경로가 해답을 찾을 가능성이 없음을 의미
• 가지치기(pruning) : 유망하지 않은 하위 트리를 자르는 것

백트래킹 vs DFS ?

공통점

• 두 방법 모두 깊이 우선 탐색 (DFS, Depth-First Search)을 이용하여 탐색합니다.
• 재귀 함수를 사용하는데, 이 때 스택(stack) 메모리를 사용하여 작동합니다.

차이점

1. 목적
   • DFS: 모든 노드를 방문하는 것이 목적입니다. 경로 자체에 관심이 있습니다.
   • 백트래킹: 주로 결정 문제(Decision Problem)에서 해를 찾는 것이 목적입니다. 가능한 모든 상태 공간을 탐색하지 않고, 해를 찾을 가능성이 없다고 판단되는 순간 해당 경로의 탐색을 중단합니다.
2. 가지치기(Pruning)
   • DFS: 모든 경로를 탐색합니다.
   • 백트래킹: 해결책으로 이어질 가능성이 없는 경로는 더 이상 탐색하지 않습니다. 이러한 과정을 가지치기라고 합니다.
3. 응용
   • DFS: 그래프와 트리의 모든 노드를 방문하는데 사용됩니다. 연결성을 확인하는 경우, 사이클 탐지, 연결 요소 찾기 등에 사용됩니다.
   • 백트래킹: 조합, 순열, 해밀턴 경로, N-Queens 문제, 미로 찾기 등의 문제에 사용됩니다.

정리

• 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것을 말합니다. 즉, 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것입니다.
• 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.

작동 원리

1. 시작점에서 시작한다.
2. 현재의 선택지 중 하나를 선택한다.
3. 새로운 선택이 해결책을 찾는 데 도움이 되는지 확인한다.
4. 만약 새로운 선택이 유망하다면, 다음 단계로 나아간다.
5. 그렇지 않다면, 가장 최근의 선택지로 돌아가 다른 경로를 탐색한다.(Backtracking)
6. 모든 가능한 선택과 경로를 탐색할 때까지 2-5 단계를 반복한다.

적용 사례

• N-Queens: N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제.
• 미로 찾기: 주어진 미로에서 시작점에서 종료점까지의 경로를 찾는 문제.
• 순열 생성: 주어진 집합의 모든 가능한 순열을 생성하는 문제.

N과 M

15649번: N과 M (1)

조합

import itertools

n, m = map(int, input().split())
nums = [i for i in range(1, n+1)]

array = itertools.permutations(nums, m)

for i in array:
    for j in i:
        print(j, end = ' ')
    print()

백트래킹

import sys
input = sys.stdin.readline

def backtracking():
    if len(array) == m:
        print(" ".join(map(str, array)))
        return

    for i in range(1, N + 1):
        if i not in array:
            array.append(i)
            backtracking()
            array.pop()

N, M = map(int,input().split())
array = []

backtracking()

N-Queens

9663번: N-Queen

def is_safe(board, row, col, n):
    # 해당 열에 퀸이 있는지 확인
    for i in range(row):
        if board[i] == col:
            return False
        # 대각선에 퀸이 있는지 확인
        if board[i] - i == col - row:
            return False
        if board[i] + i == col + row:
            return False
    return True

def n_queen(board, row, n):
    if row == n:
        return 1
    count = 0
    for col in range(n):
        if is_safe(board, row, col, n):
            board[row] = col
            count += n_queen(board, row + 1, n)
    return count

def solve_n_queen(n):
    board = [-1] * n
    return n_queen(board, 0, n)

n = int(input())
result = solve_n_queen(n)
print(result)