📌 백트래킹이란?
백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하는 방법이다.
원하는 값이 아닐 경우 더 이상 탐색을 진행하지 않고 전 단계로 back해서 돌아가는 방법으로 이름 그대로 backtracking 알고리즘이다.
📌 백트래킹 vs DFS
두 알고리즘 모두 탐색 알고리즘이라는 점에서는 동일하다.
그렇다보니 백트래킹 문제는 dfs로, dfs문제는 백트래킹을 사용해서 대부분 문제를 해결할 수 있다.
나도 처음에는 둘의 차이를 거의 못느꼈고 그냥 자주 쓰는 방법으로만 풀고는 했다.
결론적으로는 백트래킹 알고리즘이 좀 더 효율적이다!
dfs는 원하지 않는 경우더라도 트리의 바닥까지 모든 경우의 수를 탐색하지만 백트래킹 알고리즘은 불필요한 탐색을 하지 않는다는 점 때문이다.
💡 Example
백트래킹에 대해 알아보기 위해 조금이라도 서칭을 해봤다면 대표적으로 만날 수 있는 예시 문제이다.
BOJ의 N과 M이라는 문제이다.
이 문제는 기본적인 문제를 시작으로 약 7개 이상의 문제가 존재하는데 제일 기본적인 N과 M(1) 을 봐보자.
문제는 아래와 같이 매우 간단하다!
python을 사용하는 사람이라면 백트래킹 또는 dfs 알고리즘을 사용하지 않고 단순 내장 함수를 사용해서 풀 수도 있다는 걸 알 것이다.
하지만! 이 문제의 취지는 백트래킹인 만큼 이를 활용해서 풀어보자.
N, M = map(int, input().split())
answer = []
def back():
# 원하는 길이의 순열이 완성되면 출력
if len(answer) == M:
print(" ".join(map(str, answer)))
return
# i는 1부터 N까지의 숫자
for i in range(1, N + 1):
# 순열이므로 겹치는지 아닌지 확인
# 중복이 아니면 숫자 i를 리스트에 추가
if i not in answer:
answer.append(i)
back()
# return 되서 돌아오면 전 단계로 돌아감
# 예를 들어 순열이 1,2,3이면 return 되서 돌아온 후 3이 pop되고
# 1,2에서 다음 값을 찾는 형식으로 전 단계로 돌아가는 것
answer.pop()
back()
처음에 이 문제를 풀어볼 때는 백트래킹과 dfs를 구별하지 못할 때 풀었던 문제로 answer.pop() 단순 순열을 만들기 위해 리스트를 만드는 과정이라고 생각했지만 이번 포스팅을 하며 백트래킹에 대해 알아보고 자세히 주석을 달아보니 저 부분이 백트래킹 알고리즘의 핵심 부분이라는 것을 이해할 수 있었다!
이를 활용해서 어려운 문제도 한 번 풀어봐야겠다🧐
-오늘의 포스팅 끝-
