[백준] 15650번 N과 M(2) / 파이썬(python)

# 문제 링크

www.acmicpc.net/problem/15650

15650번: N과 M (2)

# 관련 알고리즘 이론

jiwon-coding.tistory.com/34

백트래킹 (Backtracking)

# Soultion

15649번과 거의 동일하지만 이 문제에서는 [1,2], [2,1]과 같은 경우는 중복되는 경우로 보고 [1,2]만 출력해야한다.

# 15649
n,m = list(map(int,input().split()))
s = []
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()
 

# 15650번
n,m = list(map(int,input().split()))
s = []
def dfs(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start,n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)
 
    

 

4. 소스를 보면 알수있듯이 15649번과 동일하지만, start 변수만 추가를 해주었다.

8. 기존에는 1부터 n까지 모든 숫자를 사용했지만 [2,1]과 같이 앞의숫자가 뒤의숫자보다 작은경우를 제외하기위해 start부터 n까지 숫자를 사용한다.

12. 재귀함수를 호출할때는 i를 이용하여 자신의 다음숫자를 부르게된다.

 

 

---

동작과정을 간단하게 표현해봤습니다.