완전 탐색과 백트래킹

완전 탐색 문제를 푸는데 백트래킹을 알아야 시간 내에 풀리는 문제들이 많았다.

왜 완전 탐색 유형 문제인데 백트래킹이 나오지 하는 의문을 갔고

일단 나왔으니까 풀어야지 하는 생각을 풀었는데

알고보니,

백트래킹은 완전 탐색을 개선한 형태의 탐색 방식이었다.

 

완전 탐색

 

모든 경우를 탐색해가면서

무언가를 세거나 어떤 조건이 가능한 경우가 있는지 확인하는 방법

 

DFS/BFS도 결국 완전 탐색의 한 유형으로 이해할 수 있다.

 

사용하는 경우

• 발생 가능한 경우의 수가 충분히 적은 경우
• 따져야 하는 상황이 특정 규칙에 따라 발생하지 않는 경우
• 각각의 경우에 따져야 하는 상황이 명확한 경우

사용하는 방법

• 발생 가능한 모든 경우를 찾아낸다
• 각각의 경우에 대해 조건에 부합하는지 판단한다

 

백트래킹

 

재귀를 이용한 완전 탐색 방식으로,

해를 찾는 도중 유망하지 않은 경로라 생각되면

되돌아가서 해에 도달할 가능성이 있는 경로에 대해 탐색을 수행하는 방법

 

재귀를 사용하기 때문에 DFS의 방식을 빌린다.

 

백트래킹과 DFS의 차이점

 

백트래킹 기본 코드

def backtracking(n):
	if 정답이면:
    	정답일 때 수행하는 작업 (저장 or 출력)
        return
    else 정답이 아니면:
    	for 모든 자식 노드에 대해서:
        	if 유망한지확인(m):
            	n 상태변화
                backtracking(n+1)
                n 원상복구
                
                
def 유망한지확인(m):
	if 조건에 안맞으면:
    	return False
    return True

 

 

 

참고 자료

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

https://velog.io/@mincastle98/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

https://velog.io/@kjyeon1101/%EC%BD%94%ED%85%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-class-4-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking