백준 #15650

문제 바로가기

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입출력 규칙

1. 입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

2. 출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

문제접근

이번 문제는 DFS 방식으로 백트래킹 기법을 이용하는 접근방식으로 풀었다.
DFS는 깊이 우선 탐색으로 한지점에서 간선을 타고 도착지점까지 계속 탐색한 후 다시 돌아와 다른지점에서 탐색하는 방식으로 한방향으로 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기하고, 다시 왔던 길로 되돌아와 다른 선택지로 다시 탐색하는 것이다. 백트래킹은 재귀로 보통 구현하며, 안되는 조건을 없애면서 탐색하기에 시간복잡도를 줄일 수 있다.

백트래킹을 위해 우선 가능성이 판단되는 유무를 확인하기 위해 True, False 값을 담아놓을 수 있는 배열을 만든 후, 값의 비교를 통해 가능성 판단을 결정해야하므로 값을 저장해놓을 수 있는 배열을 만든다. 그리고 재귀함수를 통해 숫자를 +1씩 증가시키면서 Print 문의 조건을 충족시켜 출력되게 한다.

문제풀이(Python)

    
N, M = map(int, input().split(" "))
lst = [i for i in range(1, N+1)]
check_list = [False]*N

arr = []
def dfs(cnt):
    if cnt == M:
        print(*arr)
        return
    
    for i in range(N):
        if check_list[i]:
            continue
        check_list[i] = True
        arr.append(lst[i])
        dfs(cnt+1)
        arr.pop()
        
        for j in range(i+1, N):
            check_list[j] = False

dfs(0)