백트랙킹

• 해를 찾는 과정에서 막히면 되돌아가서 다른 경로를 시도하는 기법
• 일반적인 DFS와 차이가 있다면 가지치기를 한다는 점.
  즉, 모든 경우의 수를 탐색하는 대신 조건을 걸어 유망하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서 다른 경우를 탐색

DFS와 백트래킹 (BackTracking)

DFS (Depth-First Search)

• 깊이우선탐색으로 가능한 모든 경로를 탐색.
• 모든 경로를 탐색하는 특징으로 불필요할 것 같은 경로를 사전에 차단하지 않기 떄문에 경우의 수를 줄이진 못함.

백트래킹 (BackTracking)

• 알고리즘 기법 중 하나로 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어감.

예시

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

해당 문제의 경우 m으로 자리 수를 정해놓고 각 자리에 들어가는 수는 중복되지 않음.
예를 들어, n = 4, m = 2인 경우 -> 자리 수는 2개, 첫번째 자리에 1이 오는 경우에는 둘째 자리에는 1을 제외한 나머지 숫자만이 올 수 있음

-> 이미 사용(방문)한 경우를 제외

for i in range(1, n+1):
	if visited[i]:
    	continue

입력값을 받고 리스트를 만들어줌.
이때 s는 출력을 위한 값을 담아두는 스택

n, m = map(int, input().split(" ")
s = []
visited = [False] * (n+1)

DFS 함수는 구현시 재귀로 반복 호출되기 떄문에 출력할 함수에 대한 조건을 먼저 걸어줌.
리스트 안에 미리 받은 m개의 요소가 들어갈 경우, 출력하도록 구현.

def dfs():
	if len(s) == m:
    	print(''.join(map(str, s)))
     	return

위의 조건을 만족하지 않을 경우, 아직 방문하지 않았을 경우에만 방문하도록 구현.
방문하면 해당 값을 True로 바꿔주고, 해당 값을 s에 추가시켜 다시 dfs()를 호출하도록 구현.

def dfs():
	if len(s) == m:
    	print(''.join(map(str, s)))
        return
    for i in range(1, n+1):
    	if visited[i]:
        	continue
        visited[i] = True
        s.append(i)
        dfs()
        s.pop()
        print(s)
        visited[i] = False

n, m = map(int, input().split(" ")
s = []
visited = [False] * (n+1)

dfs()
        

주로 조합, 순열, NP-Hard 문제에서 사용됨