문제 링크: https://www.acmicpc.net/problem/15652

Thumbnail: Photo by Iqbal Pohan (Unsplash)

백트래킹 문제 시리즈, N과 M의 4번째 문제입니다.

풀이

​백트래킹으로 풀이할 수 있습니다.

백트래킹이란, 모든 분기를 다 탐색하되 유망하지 않은 분기는 탐색에서 제외하는 방법입니다. 여기서 유망하지 않다를 판단하는 기준은 문제 조건을 기반으로 합니다.

유망하지 않다?

문제에서 요구하는 정답 수열의 조건은 다음과 같습니다.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 \(A_1\) ≤ \(A_2\) ≤ ... ≤ \(A_{K-1}\) ≤ \(A_K\)를 만족하면, 비내림차순이라고 한다.

여기서, 수열의 길이가 \(M\)인 것과 같은 수를 여러 번 고르는 것은 탐색의 방법을 조절하면 되니 굳이 조건에 포함하지 않아도 됩니다. 따라서, 실제로 탐색하려는 분기가 유망한지 판단하는 기준은 이 수열이 비내림차순인가? 입니다.

DFS - 너비 우선 탐색

​​이제, DFS를 통해 수열을 만들되, 유망하지 않은 분기는 탐색하지 않게 구현해봅시다. 먼저 1부터 \(N\)까지의 수를 가지고 길이 \(M\)의 수열을 만드는 기본적인 DFS의 형태를 알아봅시다.

N, M = map(int, input().split())
array = [0 for _ in range(M)]

def dfs(depth):
    if depth == M:  # 재귀의 종료 조건
        print(" ".join(map(str, array)))
        return
    for i in range(N + 1):
        array[depth] = i
        dfs(depth + 1)
        array[depth] = 0

dfs(0)

​이 코드의 경우, 문제에서 원하지 않는 내림차순 수열까지도 만들어내게 됩니다.
그렇다면, 어떻게 내림차순 수열을 제외할 수 있을까요?

바로, 다음 탐색 분기로 진입하는 과정인 dfs(...)의 호출을 조절해주면 됩니다. 이는 조건문으로 가능합니다.

def dfs(depth, prev):
    if depth == M:  # 재귀의 종료 조건
        print(" ".join(map(str, array)))
        return
    for i in range(N + 1):
        if i >= prev:
            array[depth] = i
            dfs(depth + 1, i)
            array[depth] = 0

dfs(0, 1)

위 코드에서는 dfs 함수의 인자로 이전 분기에 선택한 수를 받아서, 다음 분기가 적절한지 판단하는데 사용하고 있습니다.

### 조건문 단순화

조건문을 보면, 결국 prev이상 N + 1 미만으로 반복하면 되니, 굳이 조건문을 쓰는 대신에 range 의 범위를 조절해도 됩니다.

def dfs(depth, prev):
    if depth == M:
        print(" ".join(map(str, array)))
        return
    for i in range(prev, N + 1):
        array[depth] = i
        dfs(depth + 1, i)
        array[depth] = 0

dfs(0, 1)

전체 코드

input = open(0).readline
N, M = map(int, input().split())
array = [0 for _ in range(M)]

def dfs(depth, prev):
    if depth == M:
        print(" ".join(map(str, array)))
        return
    for i in range(prev, N + 1):
        array[depth] = i
        dfs(depth + 1, i)
        array[depth] = 0

dfs(0, 1)