백트래킹은 재귀적 방법을 통해 모든 경우의 수를 탐색하는 알고리즘으로, 알고리즘 문제에서 정말 자주 출제가 되는 유형이다. 백트래킹을 부르는 다른 용어로는 깊이 우선 탐색 (DFS: Depth First Search), 재귀 함수 등이 있다.
백트래킹, 즉 깊이 우선 탐색은 위의 사진과 같이 모든 경우의 수를 깊게 들어갔다가 나오는 방식으로 진행이 되는 알고리즘이다. 즉 이 문제의 경우는 1에서 4까지의 수열을 구한다고 치면 1이라는 값을 처음으로 넣었을 때 다음 깊이의 탐색에서는 2, 3, 4 중 하나를 넣고, 만약 3을 넣었다고 한다면 다음 깊이에서는 2, 4 중 하나를 넣고, 여기서 4를 골랐다면 마지막으로 2를 넣어서 모든 경우의 수를 이렇게 하나하나 체크하게 된다.
# 백트래킹 함수 (재귀적 함수)
# - 입력값
# 1. 이전까지 누적으로 담은 리스트 path
# 2. 숫자 N
# 3. 수열의 갯수 M
def backtracking(path, N, M):
# 종결조건을 넣어준다. (즉 이 함수가 끝나는 조건을 넣어준다.)
# 이 문제의 경우 수열 4개가 완성될 때가 종결 조건이다.
if (len(path) == M):
# 수열의 각 요소를 문자형으로 바꿔준다.
path = list(map(str, path))
# 그리고 프린트해준다.
print(" ".join(path))
# 마지막으로 함수를 끝내준다.
# (종결조건 안에 return이 없을 경우 함수가 무한으로 돌아간다. 따라서 무조건 넣을 것.)
return
for i in range(1, N+1):
if (visited[i] == 0):
path.append(i)
visited[i] = 1
backtracking(path, N, M)
visited[i] = 0
path.pop()
그 생각을 코드로 작성하면 위와 같게 된다. 백트래킹은 함수를 끝내도록 하는 "종결조건"이 가장 앞에 위치하고, 그 다음으로는 함수 안에서 함수를 다시 한번 더 돌리는 코드가 위치하게 된다. 하지만 이렇게 함수 안에서 함수를 다시 돌리는 코드는 잘못하면 무한하게 함수가 돌아가는 문제가 발생하게 되는데, 이러한 무한 함수 문제를 해결해주기 위해서 종결조건을 꼭 넣어주어야만 하고, 종결조건 안에 함수를 끝마치는 return 을 무조건 넣어주어야만 한다.
path.append(i)
visited[i] = 1
backtracking(path, N, M)
visited[i] = 0
path.pop()
그 외의 특징으로는 backtracking을 하기 전에 필요한 처리를 할 때, backtracking을 하고 나서는 그 필요한 처리를 다시 원상회복시켜주어야만 한다.
그 이유는 위의 사진을 통해 설명하자면, backtracking 함수가 끝났다는 것은 결국 3번 방향으로 가서 G를 이미 탐색하고 4번으로 돌아오는 과정이기 때문에 G에 대해서 처리해준 값들을 모두 다시 원상회복 시킨 후 H로 탐색을 다시 진행해야만 하기 때문이다. (이해하기가 어려운 내용이라서, 이해가 어려울 시에는 그냥 위의 사용법을 그대로 외운 후, 여러 문제들을 풀어보면서 그 감을 익히면 좋다.)
아무튼 이러한 원리를 통해 백트래킹 함수를 짤 수가 있다.
그리고 한가지 더 알아두면 좋을 점은, 코드에서 방문표시 "visited"를 사용하게 되면 각각의 요소를 딱 한번만 사용할 수 있도록 규제해줄 수 있고, 만약 이 "visited"를 사용하지 않으면 각각의 요소를 중복으로 사용할 수 있게 된다.
예를 들어 위의 결과값은 visited를 사용했을 때이다. 보면 각각의 요소가 중복되지 않도록 수열이 만들어진 것을 알 수 있다.
반면에 위의 결과값은 "visited"을 아예 다 빼주었을 때의 결과물이다. 이렇게 되면 중복도 허용하면서 수열이 만들어진다.
코드
import sys
# 입력값을 받아들인다.
N,M = map(int, sys.stdin.readline().split())
# 각각의 숫자의 방문표시를 체크하기 위해서 visited 리스트를 준비해준다.
visited = [0 for _ in range(N+1)]
# 백트래킹 함수 (재귀적 함수)
# - 입력값
# 1. 이전까지 누적으로 담은 리스트 path
# 2. 숫자 N
# 3. 수열의 갯수 M
def backtracking(path, N, M):
# 종결조건을 넣어준다. (즉 이 함수가 끝나는 조건을 넣어준다.)
# 이 문제의 경우 수열 4개가 완성될 때가 종결 조건이다.
if (len(path) == M):
# 수열의 각 요소를 문자형으로 바꿔준다.
path = list(map(str, path))
# 그리고 프린트해준다.
print(" ".join(path))
# 마지막으로 함수를 끝내준다.
# (종결조건 안에 return이 없을 경우 함수가 무한으로 돌아간다. 따라서 무조건 넣을 것.)
return
for i in range(1, N+1):
if (visited[i] == 0):
path.append(i)
visited[i] = 1
backtracking(path, N, M)
visited[i] = 0
path.pop()
backtracking([], N, M)
