[백준][20단계 백트래킹] 15650번 /N과 M (2) (파이썬/Python)

1. 문제 설명

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

2. 코드

import sys

input = sys.stdin.readline
N,M = map(int,input().split())

path = []
out = []

def dfs(start: int):
    if len(path) == M:
        out.append(" ".join(map(str,path)))
        return
    for x in range(start,N+1):
        path.append(x)
        dfs(x+1)
        path.pop()

dfs(1)
sys.stdout.write("\n".join(out))

3. 풀이 과정

N과 M (1)에서 한 가지 포인트만 변화한 문제이다.

https://litd.tistory.com/665

[백준][20단계 백트래킹] 15649번 /N과 M (1) (파이썬/Python)

수열이 오른차순으로 정렬되기 때문에 기존 코드의 결과는 많은 중복 결과가 나오게 된다.

이를 해결하기 위해 변수 start를 넣어서 오름차순을 보장하고 재귀식도 x+1로 항상 x보다 큰 값만 허용하도로 한다.

path의 길이가 M이 되면 공백으로 이어서 out에 추가하고, 재귀가 끝나면 줄바꿈으로 이어서 한줄로 출력한다.

 

4. 자투리 개념

• 백트래킹 알고리즘
  - 정답을 구성해 가는 중간 단계들을 체계적으로 탐색하되, 불필요한 가지는 일찍 잘라내는(Pruning) 깊이우선탐색(DFS)

핵심 아이디어

• 문제의 해 공간(Search Space):
  가능한 모든 해(또는 부분해)를 트리 형태로 생각합니다. 루트는 “아무 것도 선택하지 않음”, 깊이 d는 “d개 선택 완료”.
• 부분해(Partial Solution):
  아직 완성은 아니지만 제약을 만족하며 확장될 수 있는 중간 상태.
• DFS + 되돌리기(Backtrack):
  하나를 선택(choose) → 더 내려가서 탐색(explore) → 돌아오며 선택을 취소(unchoose)합니다.
• 가지치기(Pruning):
  제약을 위반하거나, 더 진행해도 정답이 절대 나오지 않을 “가지”는 즉시 탐색을 멈춥니다.

공통 템플릿

def backtrack(state):
    if 완성조건(state):
        정답 처리
        return

    for candidate in 후보집합(state):  # 보통 정렬/오름차순으로 순회
        if 제약을 만족(candidate, state):  # 가지치기 1차
            state에 candidate를 반영(choose)
            backtrack(state)
            state에서 candidate를 되돌리기(unchoose)  # 핵심