[Python] 백준 #15649 - N과 M (1)

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

15649번: N과 M (1)

 

풀이

from itertools import permutations
N,M = map(int,input().split())
arr = [i for i in range(1,N+1)]
for a in list(permutations(arr,M)):
    for i in a:
        print(i,end=" ")
    print()

순열을 사용하면 쉽게 풀수있는 문제이다..

 

 

하지만 문제의도는 백트래킹이기때문에 백트래킹으로 푼 코드를 들고와봤다!

def DFS():
    if len(s) == M:
        print(*s)
        return

    for i in range(1, N+1):
        if visited[i]:  # 이미 방문했으면 건너뜀
            continue

        # 방문 안했으면 방문체크 후, 출력 리스트에 넣음
        visited[i] = True
        s.append(i)
        DFS()  # 함수 다시 호출
        s.pop()  # 원상복귀 과정 필요
        visited[i] = False


        
N, M = map(int, input().split())  # N:주어진 수, M:수열의 길이
s = []  # 출력 수열 넣을 리스트 (stack)
visited = [False] * (N+1)  # 방문체크 할 리스트
DFS()

 

 

 

출처-https://jennnn.tistory.com/7