<백트래킹> 15649번 N과 M (1) with 파이썬

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

 

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

정답비율

60.352%

알고리즘 분류

 #백트래킹

def backtrack(lst, index):
    if lst[-1] > 0 :
        print(' '.join(map(str, lst)))
    else :
        for num in range(1, n+1):
            if visited[num]:
                continue
            visited[num] = True
            lst[index] = num
            backtrack(lst, index + 1)
            lst[index] = 0
            visited[num] = False

global n,m, visited
n, m = map(int, input().split())
answer = [0] * m
visited = [False] * (n+1)
backtrack(answer, 0)

 

 - 백트래킹 문제는 처음이라 백준에서 가장 기본문제를 풀어보았다.

 

 - 백트래킹은 기본적으로 재귀를 사용하며, 원하는 답을 이끌어낼때까지 자식노드를 탐색하고 다시 거슬러올라오는 방식이다.

 

 - 답을 도출해낼 answer리스트와, 방문처리를 위한 visited 리스트를 먼저 할당한 후 함수를 시행한다.

 

 - answer의 가장 마지막 원소에 값이 있다면 이는 원하는 답을 이끌어 낸 것이므로 출력한다.

 

 - 그렇지 않다면, 아직 좀 더 탐색해야하므로 visited를 통해 이미 사용한 숫자인지를 확인한다. 그리고 사용한 숫자가 아니라면 방문처리를 한후 answer에 넣는다. 그 상태로 그 다음 자릿수를 구하기 위해 재귀를 시작한다. 해당자리에서의 재귀가 끝나면 방문처리와 원소값을 초기화한다.(부모노드로 올라간다)

 

 

---

 

참고

 

15649번: N과 M (1)