백준 15649 풀이 (재귀함수, 백트래킹)

음 백트래킹이 먼지 몰랐다. 그래서 여기저기 기웃거려본 결과 트리를 만들때 불필요한걸 쳐내면서 트리를 만드는거 같다. 물론 이 문제에 백트래킹을 어떻게 적용해야하는지 전혀 이해못했다.

그냥 재귀함수로 적용해서 풀어보자! 라는 마인드로 풀었는데 어찌저찌 풀리긴 풀렸다.

 

순서는 다음과 같다.

1. 빈 리스트, n, m을 인자로 넣어준다.

2. for 을 이용하여 사용되지 않은 숫자를 리스트에 추가하며 재귀함수를 실행시킨다.

3. m을 하나씩 줄여서 m이 0이 되면 리스트에 저장된 값을 출력해준다.

n,m = map(int,input().split())
Map=[i for i in range(1,n+1)]

def back(tlist, n,m):
    if m == 0:
        for i in tlist:
            print(Map[i],end=' ')
        print()
        return

    for i in range(n):
        if i not in tlist:
            tlist.append(i)
            back(tlist,n,m-1)
            tlist.pop()

back([],n,m)

 그렇게 풀었더니 어찌저찌 풀렸다.

재귀함수가 너무 어렵게 느껴졌는데 이번에 쉬운 문제를 풀었더니 나름 자신감이 상승했다. 좋다.