백트래킹 (Backtracking) 알고리즘

00 개요

• 목표: 코딩테스트 뽀개기!

01 백트래킹

1. 백트래킹이란

• DFS와 같이 모든 경우의 수를 확인해야 할 때 사용됨
  • DFS: 가능한 모든 경로(후보) 탐색, 그러나 불필요할 것 같은 경로를 사전에 차단하는 행동이 없으므로 경우의 수를 줄이지 못함 (i.e., N!가지 경우의 수를 가진 문제에는 적합하지 않음)
• for로는 확인 불가능한 경우 (깊이가 달라지는 경우)
• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가야 되는 경우 
• 모든 가능한 경우의 수 중 특정 조건을 만족하는 경우만 살펴봐야 하는 경우
• 즉, 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 해야하는 경우
• 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현

2. 준비하기

1) 아이디어

• 1부터 N중에 하나를 선택한 뒤
• 다음 1부터 N부터 선택할 때 이미 선택한 값이 아닌 경우 선택
• M개를 선택할 경우 프린트

2) 시간 복잡도

• N^N: 중복 가능, N = 8까지 가능
• N!: 중복 불가, N=10까지 가능

3) 자료구조

• 방문 여부: bool [ ]
• 선택한 값 입력: int [ ]

 

3. 연습 문제: 백준 15649

• 링크: https://www.acmicpc.net/problem/15649

1) 문제

• Q:
  • 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 입력:
  • 첫째 줄에 자연수 N과 M이 주어진다. (1 <= M <= N <= 8)
• 출력:
  • 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
• 예제 입력 1:

3 1

• 예제 출력 1:

1 2 3

• 예제 입력 2:

4 2

• 예제 출력 2:

1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3

2) 사전 계획 수립

• 아이디어
  • 백트래킹 재귀 함수 안에서, for 돌면서 숫자 선택 (이때 방문 여부 확인)
• 시간 복잡도
  • 중복 불가 => N! 사용
  • N = 8 => 가능!
• 자료구조
  • 방문 여부 확인: bool [ ]
  • 결과값 저장: int [ ]

3) 실습

# input이 있을 경우
import sys
input = sys.stdin.readline
# N, M = map(int, input().split())

N, M = 3, 2
result = []                     # 순열을 담을 리스트
chk_list = [False] * (N + 1)    # 방문 여부 확인

def recur(num):
    global result
    if num == M:
        print(' '.join(map(str, result)))
        return    # 함수 종료
    for i in range(1, N+1):
        if chk_list[i] == False:
            chk_list[i] = True     # 방문 여부 확인
            result.append(i)       # 순열 리스트에 포함
            recur(num+1)           # 재귀 함수
            result.pop()           # 마지막 숫자 제거
            chk_list[i] = False    # 다음을 조회하기 위해 방문 여부 초기화

recur(0)	# 0부터 시작

• 결과값 (N, M = 3, 2)

• 결과값 (N, M = 4, 3)

4) 파이썬 내장 함수 활용 (백준 15649에 한하여)

# 파이썬 내장 함수 활용
from itertools import permutations

N, M = 3, 2

permutations_list = []
for perm in permutations(range(1, N+1), M):
    permutations_list.append(list(perm))
    
temp_list = [' '.join(list(map(str, list(a)))) for a in permutations_list]
for i in temp_list:
    print(i)

• 결과값 (N, M = 3, 2)

• 결과값 (N, M = 4, 3)

참조

1. 개발자 장고, https://www.youtube.com/watch?v=atTzqxbt4DM&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=4
2. 알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제 https://chanhuiseok.github.io/posts/algo-23/ 
3.