Skip to content

7, 8주차 백트래킹

Jump to bottom
Wonjun You edited this page Mar 20, 2023 · 1 revision

백 트래킹 기법의 이해

1. 백 트래킹 (backtracking)

  • 백트래킹 (backtracking) 또는 퇴각 검색 기법이라고 부름

  • 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략

    • 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법

  • 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현

    • 각 후보군을 DFS 방식으로 확인
    • 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
      • Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
      • Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

  • 일반적인 코드 구조

    def dfs():
    global s  # 현재 상태를 담는 변수

    # 탈출구: 정상적으로 탐색을 완료했을 경우
    if condition:
        ''' 코드 블럭 ''' 
        return

    # 반복문으로 후보군 탐색
    for candidate in candidate_list:
        # 제약조건 만족 여부 확인
        if valid(candidate):
            # 현재 상태 업데이트
            ''' 코드 블럭 ''' 

            dfs()

            # 현재 상태 초기화(되돌리기)
            ''' 코드 블럭 '''

2. 기본 예제 - [15649] N과 M (1)

문제 링크: https://www.acmicpc.net/problem/15649

정답 코드

# Promising
# 지금 같이 간단한 조건이면 별도의 함수로 분리할 필요가 없지만,
# 복잡한 제약 조건일 경우 별도의 함수로 모듈화하는 것이 나음 
def valid(n):
    global s
    return n not in s

# Backtracking
def dfs():
    global s # 현재 상태를 담는 변수
    # 탈출구 정상적으로 탐색을 완료했을 경우
    if len(s) == m:
        print(' '.join(map(str, s)))
        return

    # 반복문으로 후보군 탐색
    for i in range(1, n+1):
        # 제약조건 만족 여부
        if valid(i):
            # 현재 상태 업데이트
            s.append(i)

            dfs()
            # 현재 상태 초기화(되돌리기)
            s.pop()


n, m = list(map(int, input().split()))
s = []

dfs()

3. 심화 예제 - [2580] 스도쿠

문제 링크: https://www.acmicpc.net/problem/2580

image

핵심 제약 조건

  • 빈칸에 들어갈 수는 그 행의 숫자들과 중복되어서는 안 된다.
  • 빈칸에 들어갈 수는 그 열의 숫자들과 중복되어서는 안 된다.
  • 빈칸에 들어갈 수는 굵은 선으로 구분되어 있는 3x3 정사각형 안의 숫자들과 중복되어서는 안 된다.

풀이 절차

  1. 각 행, 각 열, 각 그룹(3X3 정사각형)에서 1~9의 숫자들의 사용여부를 확인하는 전역변수를 만든다
  # 편의상 index값을 숫자를 의미하게 하고, 0은 이미 사용한 것으로 봄
  row_numbers = [[True] + [False] * 9 for _ in range(9)]
  col_numbers = [[True] + [False] * 9 for _ in range(9)]
  group_numbers = [[True] + [False] * 9 for _ in range(9)]
  1. dfs를 통해 스도쿠 판을 한 칸 한 칸 씩 확인한다.

예> dfs(0,0) -> dfs(0,1) -> dfs(0,2) -> ... -> dfs(0,8) -> dfs(1,0) ...

  1. 빈칸일 경우, 1~9까지의 숫자들을 반복문으로 돌아가며 사용가능여부를 확인한다.

조건: 후보 숫자는 해당 (row, col)을 기준으로 row_numbers, col_numbers, group_numbers에서 사용되지 않는(False) 수여야 함

  1. 사용가능한 숫자가 있는 경우 현재 상태를 업데이트 후 다음 dfs로 넘어가고, 모든 숫자가 유효하지 않다면 자동으로 이전 dfs로 돌아가게(return) 한다.
  2. 다음 단계 dfs에서 돌아오면, 현재 상태를 다시 되돌리고 다음 후보 숫자로 반복문이 넘어가게 한다.
  3. dfs가 (8,8)까지 탐색되어 (9,0)으로 넘어가면 모든 스도쿠 칸이 채워진 것으로 보고, 스도쿠 판을 출력한다.

정답 코드

import sys


def get_group_idx(row, col) -> int:
    return row // 3 * 3 + col // 3


def update_state(row, col, number, undo=False):
    # 현재 상태를 담는 변수
    global row_numbers, col_numbers, group_numbers

    state = False if undo == True else True
    row_numbers[row][number] = state
    col_numbers[col][number] = state
    gid = get_group_idx(row, col)
    group_numbers[gid][number] = state


def is_valid(row, col, number):
    # 현재 상태를 담는 변수
    global row_numbers, col_numbers, group_numbers
    if row_numbers[row][number] or col_numbers[col][number]:
        return False

    gid = get_group_idx(row, col)
    if group_numbers[gid][number]:
        return False

    return True


def simulate(row, col):
    # 현재 상태를 담는 변수
    global sudoku

    # 탈출구 정상적으로 탐색을 완료했을 경우
    if row == 9:
        return True

    if sudoku[row][col] != 0:
        nrow = row + (col + 1) // 9
        ncol = (col + 1) % 9
        return simulate(nrow, ncol)

    # 반복문으로 후보군 탐색
    for number in range(1, 10):
        # 제약조건 만족 여부
        if is_valid(row, col, number):
            # 현재 상태 업데이트
            sudoku[row][col] = number
            update_state(row, col, number)

            # 다음 dfs 탐색
            nrow = row + (col + 1) // 9
            ncol = (col + 1) % 9
            complete = simulate(nrow, ncol)
            if complete:
                return True

            # 현재 상태 초기화(되돌리기)
            sudoku[row][col] = 0
            update_state(row, col, number, undo=True)

    return


input = sys.stdin.readline

sudoku = [list(map(int, input().split())) for _ in range(9)]

row_numbers = [[True] + [False] * 9 for _ in range(9)]
col_numbers = [[True] + [False] * 9 for _ in range(9)]
group_numbers = [[True] + [False] * 9 for _ in range(9)]
blanks = set()
for row in range(9):
    for col in range(9):
        number = sudoku[row][col]
        update_state(row, col, number)


simulate(0, 0)
for li in sudoku:
    print(*li)

함께 공부할 문제 리스트 - (1)

난이도 문제명 분류
[15649] N과 M (1) 백트래킹
[15650] N과 M (2) 백트래킹
[15651] N과 M (3) 백트래킹
[15652] N과 M (4) 백트래킹
[15654] N과 M (5) 백트래킹
[15655] N과 M (6) 백트래킹
[15656] N과 M (7) 백트래킹
[15657] N과 M (8) 백트래킹
[15663] N과 M (9) 백트래킹
[15664] N과 M (10) 백트래킹
[15665] N과 M (11) 백트래킹
[15666] N과 M (12) 백트래킹
[1182] 부분수열의 합 브루트포스 알고리즘 백트래킹
[9663] N-Queen 브루트포스 알고리즘 백트래킹
[2580] 스도쿠 백트래킹

함께 공부할 문제 리스트 - (2)

난이도 문제명 분류
[14888] 연산자 끼워넣기 브루트포스 알고리즘, 백트래킹
[1759] 암호 만들기 수학, 브루트포스 알고리즘, 조합론, 백트래킹
[10819] 차이를 최대로 브루트포스 알고리즘, 백트래킹
[1987] 알파벳 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 백트래킹
[2661] 좋은수열 백트래킹
Lv.3 단어 변환 백트래킹
Lv.3 여행 경로 백트래킹
Clone this wiki locally