백준-15649-백트래킹 1

백트래킹이란? 

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 알고리즘

반복문의 횟수까지 줄일 수 있으므로 효율적이다. 가지치기 (반복문 횟수 줄이기)에 따라 성능이 좌우된다. -최악의 경우에는 여전히 지수함수 시간이 걸린다

-즉, 특정한 조건을 만족하는 경우만 살펴보는 것이다.

주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어 답이 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.

 

백트래킹 코드 진행 방향

• - 탐색 여부 파악
• - 결과 리스트에 저장
• - 재귀함수 
  • 깊이가 M인 경우 탈출 (미탐색 시 진행 for 중복제거)
  • 탐색 시작 시 탐색여부 바꿔주고 탐색 내용 append
  • 탐색 후 탐색내용 pop , i++

코드

N, M  = map(int,input().split())
 
visited = [False]*N
result = []
 
def solve(depth, N,M) :
    if depth == M :
        print(' '.join(map(str,result)))
        return 
    for i in range(len(visited)) : 
        if visited[i] == False :  
            visited[i]=True
            result.append(i+1)
            solve(depth+1,N,M) # 깊이 우선 탐색 
            visited[i]=False
            result.pop()
            
solve(0,N,M)
 

 

 

 

참고: https://wlstyql.tistory.com/56