[백준] 15469번 N과 M (1) | 파이썬 Python

문제

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

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

 

입력

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

 

출력

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

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

 

예제

 

나의 풀이1

N, M = map(int, input().split())

nums = []
visited = [False]*(N+1)

def backtracking():
    if len(nums) == M:
        print(*nums)
        return
    
    for i in range(1, N+1):
        if not visited[i]:
            nums.append(i)
            visited[i] = True
            backtracking()

            nums.pop()
            visited[i] = False
            
backtracking()

• 백트래킹, 즉 DFS로 모든 노드를 깊이 우선 탐색하면서 더 이상 탐색할 필요가 없는 노드는 제외하는 가치지기(pruning)가 추가된 알고리즘 기법을 이용해서 풀었다.
• 재귀 함수를 이용해 노드마다 방문 여부를 확인하며 순열을 생성한다. 
  • nums.pop()은 이전 상태로 되돌려 새로운 조합을 만들 수 있는 역할을 한다.
    • 예를 들어 n=3, m=2일 때
    • i=2, s = [2] -> [2, 1] -> [2] -> [2, 3] 로 출력 후 pop() 하며 탐색을 진행한다.

 

나의 풀이2

N, M = map(int, input().split())
nums = []

def backtracking():
    if len(nums) == M:
        print(*nums)
        return
    
    for i in range(1, N+1):
        if i not in nums:
            nums.append(i)
            backtracking()
            nums.pop()
            
backtracking()

• visited로 방문 여부를 따로 관리하지 않아도 문제를 풀 수 있다.
• 다만 첫 번째 방법보다 실행 속도가 약간 더 느리다.

 

참고

• [Python] 백준 알고리즘 온라인 저지 2693 N번째 큰 수