[백준] 15651 : N과 M (3) (Python/파이썬)

문제 링크

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

문제

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

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

입력

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

출력

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

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

예제

입력

4 2

출력

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

---

정답 및 풀이

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
visited = [False]*(n+1)
result=[]

def dfs():
    if len(result)==m:
        print(*result)
        return

    for i in range(1,n+1):
        if not visited[i]:
            result.append(i)
            dfs()
            visited[i] = False
            result.pop()

dfs()

1. import sys
   • 빠른 입력을 사용하기 위해 sys 모듈을 불러온다.
2. input = sys.stdin.readline
   • 입력 속도를 높이기 위해 readline 사용.
3. n, m = map(int, input().split())
   • n: 사용할 숫자의 범위 (1 ~ n)
   • m: 수열의 길이
4. result = []
   • 현재 만들고 있는 수열을 저장하는 리스트
5. def dfs():
   • 중복 순열을 만들기 위한 DFS 함수
6. if len(result) == m:
   • 수열의 길이가 m이 되면
7. print(*result)
   • 완성된 수열을 공백으로 출력
8. for i in range(1, n + 1):
   • 1부터 n까지 모든 숫자를 순서대로 시도
9. result.append(i)
   • 현재 숫자 i를 수열에 추가
10. dfs()
    • 다음 자리를 채우기 위해 재귀 호출
11. result.pop()
    • 마지막에 추가한 숫자를 제거 (백트래킹)
12. dfs()
    • DFS 탐색 시작

---