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

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

정답 코드 및 설명

import sys
input = sys.stdin.readline

def DFS(N, M, sequence=[]):
    # 수열의 길이가 M에 도달했을 때, 수열을 출력하고 재귀 호출을 종료
    if len(sequence) == M:
        print(' '.join(map(str, sequence)))
        return
    
    for i in range(1, N + 1):
        # 현재 수열에 i가 포함되어 있지 않으면 추가
        if i not in sequence:
            sequence.append(i)  # 숫자 i를 수열에 추가
            DFS(N, M, sequence)  # 다음 숫자를 선택하기 위해 재귀 호출
            sequence.pop() # 백트래킹: 마지막에 추가된 숫자를 제거하고 다음 선택을 위해 되돌림

N, M = map(int, input().strip().split())
DFS(N,M)

백트래킹은 해를 찾아가는 도중에 막히면, 즉 해가 아니라고 판단되면 이전 분기로 돌아가 다시 해를 찾아가는 방법이다. 이러한 방식으로 불필요한 경로를 최소화하며 해답에 도달할 수 있다.

코드는 주어진 N과 M 값에 대해 1부터 N까지의 숫자 중에서 중복 없이 M개를 고른 수열을 모두 찾아 출력한다.

백트래킹의 적용: 숫자를 하나 선택하고, 그 선택이 최종 해답으로 이어질 수 있는지 탐색한다. 만약 현재까지의 선택이 해답으로 이어질 수 없다고 판단되면, 마지막에 선택한 숫자를 빼고 다른 선택을 시도한다.

예를 들어, N=3, M=2라고 하자.

1. 처음에 빈 수열에서 시작한다.
2. 숫자 1을 수열에 추가하고, DFS를 재귀적으로 호출한다.
3. 이제 수열은 [1]이다. 다음 숫자로 2를 추가할 수 있다.
4. 수열 [1, 2]가 되며, M=2이므로 이 수열을 출력한다.
5. 이후, 백트래킹을 통해 2를 수열에서 제거하고, 다음 숫자인 3을 시도한다.
6. 수열 [1, 3]을 출력하고, 다시 백트래킹한다.
7. 1을 수열에서 제거하고, 다음 숫자인 2를 시도한다. 이 과정은 계속 반복된다.

이러한 방식으로 모든 가능한 수열을 시도해보며, 조건에 맞는 수열만을 찾아 출력한다. 백트래킹은 이처럼 가능한 모든 조합을 효율적으로 탐색하면서, 조건에 맞지 않는 경우는 빠르게 포기하고 다른 가능성을 탐색하는 방식으로 문제를 해결한다.