[백준/python] 5568_카드놓기

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

5568번: 카드 놓기

 

백트래킹

 

가지치기(pruning)

유망하지 않은 노드를 제외하는 것

 

관련 알고리즘 

DFS : 재귀를 통해 유망한 경로만 찾아서 탐색을 수행한다. 그 후 다시 돌아와 그 중 가장 최적의 경로를 반환한다. 

* DFS는 모든 노드의 탐색이 목적, 백트래킹 기법을 혼용하여 불필요한 탐색을 그만두는 것

백트래킹은 재귀와 가지치기를 통해 탐색을 시도, 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 탐색

 

백트래킹 기본 구조

def backtracking(x):
    if 정답:
    	출력/저장
    else:
    	for 자식노드:
            if 자식노드가 유망한지(promising): 유망하면
            	자식노드로 이동
                backtracking(x+1)
                부모노드로 이동

 

# recursion Function

n = int(input())
k = int(input())
arr = [input().strip() for _ in range(n)]

check = [0]*n
temp = []

result = set()	# 중복된 조합 없애기

def card(N):
    if N == k:
        result.add(''.join(temp))
        return

    for i in range(n):
        if check[i]: 
        	continue
        check[i] = 1
        temp.append(arr[i])

        card(N+1)

        check[i] = 0
        temp.pop()
        
card(0)
print(len(result))

['12']
['12', '112']
['12', '112', '11']
['12', '112', '11', '21']
['12', '112', '11', '21', '212']
['12', '112', '11', '21', '212', '21']
['12', '112', '11', '21', '212', '21', '121']
['12', '112', '11', '21', '212', '21', '121', '122']
['12', '112', '11', '21', '212', '21', '121', '122', '121']
['12', '112', '11', '21', '212', '21', '121', '122', '121', '11']
['12', '112', '11', '21', '212', '21', '121', '122', '121', '11', '12']
['12', '112', '11', '21', '212', '21', '121', '122', '121', '11', '12', '112']

 

 

# permutations

# 순열을 사용해서 순서를 고려한 카드쌍 도출
from itertools import permutations

n = int(input())
k = int(input())
arr = []
for i in range(n):
    arr.append(input())

temp = []
card = list(permutations(arr,k))
for i in card:
    temp.append("".join(i))

# 중복제거, result = set() 방법도 가능
result = []
for i in temp:
    if i not in result:
        result.append(i)

print(len(result))