문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
예제 입력 3
4 4
예제 출력 3
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1풀이
DFS를 이용한 순열(BacTracking)
백트래킹 기법을 사용한 순열을 생성하는 문제입니다.
n,m = map(int,input().split(' '))
s = [] # 현재 선택한 숫자들을 저장하는 리스트
def dfs():
if len(s) == m: # 기저 조건 (Base Case)
print(' '.join(map(str, s))) # 리스트 `s`를 공백으로 구분하여 출력
return # 재귀 종료
for i in range(1, n+1): # 1부터 n까지 반복
if i not in s: # 중복 없이 숫자 선택
s.append(i) # 숫자 추가
dfs() # 재귀 호출
s.pop() # 백트래킹 (이전 상태로 복귀)
dfs()🔹 코드 동작 방식 상세 설명
- dfs()가 호출될 때마다 s 리스트의 길이를 확인
- len(s) == m 이면 현재 조합을 출력하고 리턴
- for 루프 (i in range(1, n+1)
- 1부터 n까지 숫자를 반복하면서 s에 추가
- 이미 선택된 숫자는 제외 (if i not in s) -> 중복 방지
- 재귀 호출 (dfs())
- s.append(i)로 숫자를 추가한 후 dfs()를 다시 호출하여 다음 숫자를 찾음
- 백트래킹(s.pop())
- dfs()가 종료되면 마지막으로 추가한 숫자를 pop()하여 이전 상태로 되돌림
🔥 핵심 개념 요약
- DFS (Depth-First Search) 를 이용하여 모든 순열을 찾는 알고리즘
- 백트래킹 (Backtracking) 기법을 사용하여 불필요한 탐색을 줄임
s리스트는 현재까지 선택한 숫자를 저장하고,pop()을 이용해 이전 상태로 되돌아감
✅ 응용
🔹 중복을 허용한 조합을 원하면?
현재 코드는 숫자를 중복 없이 선택하지만, 중복 선택을 허용하는 경우 아래처럼 변경할 수 있음.
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n+1): # 중복 허용 (숫자 선택 후 제거하지 않음)
s.append(i)
dfs()
s.pop()🎯 결론
- DFS + 백트래킹을 이용하여 길이가
m인 모든 순열을 생성 s.pop()을 사용하여 이전 상태로 되돌려 백트래킹 수행- 중복 없는 조합을 생성하는 기본적인 백트래킹 문제 🚀
