[백준/BOJ] - 5568번 python 풀이 - backtracking

---

 

처음 풀어보는 backtracking  문제.

 

방문처리를 하며 재귀적 호출을 하는 알고리즘이므로 기본적으로 방문 처리용 list인 ok를 선언하고

최종 정수의 조합을 저장하기 위한 set 자료형 rs를 선언했다. set을 선택한 이유는 중복 저장이 안되는 점을 활용

 

맨처음 재귀함수를 호출할 때 매개변수를 0으로 보내어 임시 list인 temp의 길이가 0임을 표현한다.

추후에 반복문을 통해 카드에 적힌 숫자를 temp에 넣는 과정을 할 때 마다 해당 매개변수의 값을 증가 시킨다.

매개변수 값이 뽑으려는 카드의 수만큼 도달했다면, 최종 결과 값을 저장시킬 rs에 add 해주고 return을 한다.

재귀함수에서 return을 하게 되면 이전 재귀 함수로 돌아가게 된다.

 

그렇기에 마지막으로 추가해줬던 값을 제거할 필요성이 생긴다.

해당 과정을 생략할 경우 무한정으로 temp 리스트의 값이 늘어나는 것을 볼 수 있다.

 

모든 과정을 마무리 하고 rs의 길이를 출력해주면 종료.

---

#파훼 방법
#주어진 카드 중 몇가지의 카드를 선택하는지가 유동적이므로
#반복문의 범위로 사용하면 되고 맨처음 카드의 수를 문자로 받고
#조합 별로 join으로 합친 다음, int형으로 변환.
#해당 정수가 결과리스트 저장 여부를 확인 후 최종 개수 도출
import sys
input = sys.stdin.readline
arr = [-1] #주어진 카드 담는 통
temp = []
rs = set([]) #최종 - set을 선택한 이유는 중복 선택이 안되게 하기 위함
n = int(input()) #카드수
ok = [False] * (n+1) #방문 여부
m = int(input()) #몇장 선택

for _ in range(n):
    #입력한 값의 개행문자를 제거하여 문자열에 삽입
    arr.append(int(input().rstrip()))


def btrack(num):
    if num == m: #재귀를 돌리며 뽑으려는 카드수 만큼 도달하면 return
        #temp list의 값들을 str형으로 붙여버림.
        rs.add(''.join(map(str,temp)))
        return
    for i in range(1,n+1): #0 idx에는 무의미 값을 삽입하여 1부터 시작
        if not ok[i]: #미 방문시
            ok[i] = True #방문 처리
            temp.append(arr[i]) #임시 저장소에 카드 삽입
            btrack(num+1) #임시저장소에 몇개의 수가 들어있는지의 지표
            ok[i] = False #함수에서 return을 하여 다시 돌아왔을 때 위치하는 곳. 방문처리를 false로 바꿈
            temp.pop() #temp의 마지막 값 제거

btrack(0) # 여기서 매개변수는 임시 리스트 temp의 길이를 의미

print(len(rs)) #최종 집합의 길이