백트래킹

코딩테스트

백트래킹

임지혁코딩 2024. 5. 17. 12:23

모든 경우의 수를 확인해야 할때.

하지만, FOR로는 확인이 불가능 할 때 사용한다

EX) FOR문의 수를 몇번 써야할지가 , M,N과 같은 변수로 들어올 때(변수 일때) 사용한다.

백 트래킹의 구조를 생각해보자.

1. 재귀 함수로 확인

2. 재귀를 벗어나는 조건 IF NUM == N : BREAK

(def rec (num): 일때, if num == N : break와 같은 형태로 주로 사용한다)

3. 아닐때 FOR(~~ -> 재귀)

핵심! 이 check 과정에서, 방문 여부를 확인해야한다.

시간 복잡도 확인 방법

중복이 가능할때는 N(선택할 수 있는 수) ^ M (깊이)

중복이 불가능할때는 N! (알고리즘때 들었던 내용을 기억하자) <2억이어야 한다.

방문 여부를 확인하는 자료구조, 입력을 받는 자료구조가 필요하다.

++ 순열과 같은 경우에서, 그 경우의 수들을 저장하는 순열 resultlist = []등이 필요할 수 있다.

EX) 백준 15649

import sys

N,M = map(int,sys.stdin.readline().split())

visited = [False] * (N+1)
resultlist = []

def backtracking(num):

    if num == M :
        print(' '.join(map(str,resultlist)))
        return

    for i in range(1,N+1):
        if visited[i] == False and i not in resultlist:
            visited[i] == True
            resultlist.append(i)
            backtracking(num+1)
            visited[i] == False
            resultlist.pop()

backtracking(0)