•
문제 설명
숫자의 범위(N)와 길이(M)이 주어질 때, 길이 M을 가진 중복되지 않는 수열을 구하는 문제
•
풀이 방법
평소 모듈로만 구해서 코드로 구하자니 헷갈렸는데, 그래프로 생각하면 편하다.
DFS로 길이(M)이 될때까지 숫자를 추가해주고, 이미 포함된 숫자는 제외하면 된다.(이 부분이 문제 핵심)
•
성공 코드
n, m = list(map(int, input().split()))
# 현재 구성된 수열의 정보를 저장
s = []
def dfs():
# 길이가 m과 같을 때, 출력 후 종료
if len(s) == m:
print(" ".join(map(str, s)))
return
# 1 ~ n까지 모두 확인
for i in range(1, n + 1):
# 백트래킹이 적용되는 핵심부분
# 만약 존재하지 않는 경우
# 해당 값을 순열에 추가하고, 다음 자리수 계속 확인
if i not in s:
s.append(i)
dfs()
s.pop()
dfs()
Python
복사