[Algorithm] 백트래킹(backtracking)

✨백트래킹(backtracking)

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
주요 개념은 해를 얻을 때까지 모든 가능성을 시도
트리를 검사하기 위해 깊이 우선 탐색을 사용

 

 

 

 

 

✨ 예시문제) 백준 N과 M(1)

https://www.acmicpc.net/problem/15649

 

 

 

끝나는 조건:리스트의 길이가 M이 되었을때

-> 정답목록에 해당 리스트를 추가, 종료

 

수열의 조건: 방문했던 숫자에 다시 방문하면안됨

->방문 리스트 V를 만들어서 체크 

 

 

 

 

전체 코드

import sys

def back(n,li):
    if(n==M): 
        answer.append(li)     #종료조건
        return

    for j in range(1,N+1,1):
        if(V[j]==0):
            V[j]=1
            back(n+1,li+[j])
            V[j]=0


N,M=map(int,sys.stdin.readline().rstrip().split(" "))
V=[0]*(N+1)
answer=[]

back(0,[])
for i in answer:print(*i)

 

 

 

N,M=map(int,sys.stdin.readline().rstrip().split(" "))
#N: 1~N까지의 숫자 범위 
#M:고를 수열의 수
V=[0]*(N+1)#방문체크
answer=[]#출력할목록

 

 

def back(n,li):# 현재 길이와 리스트
    if(n==M): #만약 현재 길이가 M이라면(종료조건)
        answer.append(li) #정답목록에 리스트 추가    
        return            #종료

    for j in range(1,N+1,1):#1부터 N까지의 숫자 선택
        if(V[j]==0):#만약 선택된숫자가 아니라면
            V[j]=1  #j를 선택한 숫자로 체크
            back(n+1,li+[j]) #길이+1 과 j를 추가한리스트 재귀
            V[j]=0  #방문체크 초기화

 

back(0,[])  #초기길이 0, 초기리스트 []
for i in answer:print(*i) #답 출력

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://chanhuiseok.github.io/posts/algo-23/

https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89

https://edder773.tistory.com/75