[알고리즘] 백준. #15649 N과M(1)

이번 문제는 "백트래킹(backtracking)"에 관한 문제라는데, 솔직히 백트래킹이 뭔지 몰랐다. 

*한국어로는 '퇴각 검색'이라고 한다. 

어감에서 느껴지는 의미로는 뒤로 추적해가면서 뭔갈 풀어내는 거 같긴 한데,,

 

찾아보니 문제를 푸는 모든 경우의 수를 고려하되, check point를 잡아 놔서 풀다가 막히면 check point로 돌아가 다른 풀이를 모색하는 것 같다. 

 

모든 경우의 수를 하나의 트리 형태로 구현해 놓고, 트리를 깊이 우선 탐색(dfs)을 하다가 막히면 부모 노드로 가서 다시 탐색을 하는 식인 것 같다. 여기서 부모노드가 일종의 check point 역할을 한다. 주로 재귀, 큐, 스택을 이용해서 푼다고 한다. 다시 check point로 돌아가기 위해 재귀적인 방식이나 스택을 쓰는 것 같다. (물론 재귀나 스택 모두 큰 의미에서는 비슷하다고 생각된다. ) 큐를 사용하는 것은 너비 우선 탐색 방식(bfs)를 쓸 때를 얘기하는 것 같다. 

 

깊이 우선 탐색을 하여 'F'를 찾는다면??

그러니 결국 백트래킹은 트리로 모든 경우의 수를 표현하고, 여러 탐색 기법(dfs, bfs)으로 그 경우의 수를 탐색하면서 해당 경우가 자신이 원하는 조건에 부합하는 지를 확인하고자 하는 데 쓰는 방법인 것이다. 

 

미로 찾기와 체스 경우의 수 계산 같은 여러 경우의 수를 가지치기 하여 고려한 후 그 중 답을 찾아내는 문제에 주로 사용된다고 한다. 

 

이번#15649 문제와 같은 경우, 백트래킹 카테고리의 첫번째 문제답게 백트래킹의 첫 단계인 여러 경우의 수를 구하는 문제이다. 숫자 N과 M이 주어지는데, 1~N까지의 자연수 중, 중복없이 구성할 수 있는 M개의 원소로 된 순열(permutation)을 구하는 것이다. 

 

from itertools import permutations

n, cnt = map(int, input("input: ").split())
ls = [i+1 for i in range(n)]

print("output: ")
for t in list(permutations(ls,cnt)):
    for p in t:
        print(p, end = ' ')
    print()

 

python에는 itertools라는 패키지가 있는데, 이를 이용해서 매우 쉽게 구현할 수 있다. 조합도 combination함수로 사용가능하다. 

 

패키지를 사용할 수 없는 경우를 대비해 조합(combination)과 순열(permutation) 모두 재귀적으로 구현해 보았다. 

ls = [1,2,3,4]

def combinationz(ls, n):
    ret = []
    if n == 0 or n>len(ls): 
        pass
    elif n == 1:
        ret += list(map(lambda x:{x}, ls))
    else:
        for i in range(len(ls)):
            ret += list(map(lambda x: {ls[i]}|x, combinationz(ls[i+1:], n-1)))
            
    return ret

def permutationz(ls, n):
    ret = []
    if n == 0 or n>len(ls): return ret
    elif n == 1:
        return list(map(lambda x:(x,), ls))
    else:
        for i in range(len(ls)):
            temp = [e for e in ls]
            temp.remove(ls[i])
            ret += tuple(map(lambda x: (ls[i], ) + x ,permutationz(temp, n-1)))
    return ret
            
print(combinationz(ls, 2))
print(permutationz(ls, 2))      

조합은 리턴값의 결과를 집합으로 구성되도록 했고(순서가 중요하지 않으니), 순열은 순서가 중요하니 tuple로 구성되도록 하였다.