[알고리즘/코딩테스트] 백트래킹

백트래킹

• 백트래킹 = 퇴각 검색
• 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행하는 알고리즘
• 보통 재귀로 구현하며 조건이 맞지 않으면 종료
• DFS 기반
• 보통 모든 경우의 수를 확인해야 할 때 for문으로 비교해야하는 값의 깊이가 달라져서 사용하지 못할 때가 많다
  • 이때 DFS를 이용한 백트래킹 알고리즘 사용
• 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising)
  • 만약 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버림 (Pruning)
  • 즉! DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가며 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘
• 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현
  각 후보군을 DFS 방식으로 확인
  • 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
  • Promising: 해당 루트가 조건에 맞는지를 검사하는 기법
  • Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
  • 상태 공간 트리: 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

문제를 통해 이해하기

백준 15649번 - N과 M (1)

문제

• 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열을 구하라

조건

1. 수열의 길이가 M개를 넘지 않도록
2. 배열 내의 중복인 숫자가 없어야 함

해결 과정

• 재귀 함수
  • 재귀는 탈출 조건이 필요한데, 여기에선 바로 배열의 길이가 M,
  • M이 3이라면 3에 도달했을 때
  • 길이가 3이 되었을 때, 출력하고 전 단계로 돌아가는, return을 하는 것이다.
• 그리고 사전 순으로 증가하는 순서로 수열을 채워야 하는데 그것은 for문으로 해결할 수 있다.
  • 중복은 for문으로 채울 때 if문으로 그 수가 배열 내에 존재하는지 여부를 가리고
  • 없다면 추가 아니라면 다음 수로 넘어가게 만들면 되는 것
• 정리하면 배열의 길이가 3을 넘는지 확인하고
  • 넘는다면 출력 및 return
  • 아니라면 배열을 순서대로 채우면 되는 것
    

풀이

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

def back():
	# 배열의 길이를 확인, 재귀 탈출 조건
    if len(ans) == M: 
    	# 1 2 3 이런 상태로 출력하기 위해
        print(" ".join(map(str, ans))) 
        return 
    # 1 ~ N 까지
    for i in range(1, N+1): 
    	# 중복 확인
        if i not in ans: 
        	# 배열 추가
            ans.append(i) 
            # 재귀
            back() 
            # return으로 돌아오면 이게 실행됨
            # 1, 2, 3 일때 3을 없앰으로 전 단계로 돌아가는 것
            ans.pop() 
            
back()

번외 ( 라이브러리 사용 )

• 속도 빠름, 메모리 동일

from itertools import permutations
n, m = map(int, input().split())
p = permutations(range(1, n+1), m)
for i in p:
    print(" ".join(map(str, i)))

관련 문제

• 백준 14888번 - 연산자 끼워넣기

https://veggie-garden.tistory.com/24