118. 15650(N과M (2))

N, M = list(map(int, input().split()))
S = []


def DFS(start):
    if len(S) == M:
        print(" ".join(map(str, S)))

    for i in range(start, N+1):
        if i not in S:
            S.append(i)
            DFS(i+1)
            S.pop()


DFS(1)

문제요약

DFS를 이용하여 백트래킹을 해보아라.

설명

DFS와 백트래킹에 대한 개념은 아래를 참고하자.

https://smhope.tistory.com/309

백트래킹

https://smhope.tistory.com/307

깊이 우선 탐색(DFS)

이번 문제에서는 모든 경로를 탐색하는것이 아닌 현재 노드 기준으로 탐색 후 백트래킹은 진행하나, 이미 방문한 곳은 방문하지 않는다.

 

때문에 저번 문제에서 시작부분만 추가해준다면 이미 방문한 곳은 방문하지 않게 된다.