백트래킹: 백준 15650 문제

1. 백트래킹이란?

진짜 간단하게 말하자면
아님 말고 알고리즘이다.
시도 했다가 안 되면 되돌아가서 다시 시도하면 그만인 알고리즘인 것이다.

2. 핵심개념

• 가능한 모든 경우를 체계적으로 검사하지만
• 명확하게 불가능하다면 더 진행하지 않고 이전으로 돌아감
  • 본 문제에서는 이게 pop()으로 구현됨
• 재귀함수로 구현되는 경우가 많음
• 자주 사용되는 예시
  • N-Queens 문제 (체스판에 퀸을 배치하는 문제)
  • 스도쿠 풀기
  • 부분집합의 합 문제
  • 순열/조합 생성하기
  • 비밀번호 찾는 문제

    시도1: abc123
    실패! -> 돌아가서
    시도2: abc456
    실패! -> 돌아가서
    시도3: def123

    이런것도 일종의 백트래킹!

3. 풀이

3.1 직접 구현

import sys

def generate_combinations(n: int, m: int) -> None:
    """1부터 n까지 숫자중 m개 선택하여 조합 생성"""
    
    def backtrack(start: int, combination: list[int]) -> None:
        """현재 조합을 구성하고, 조건 만족시 출력하는 백트래킹 함수"""
        
        # 조합의 길이가 목표 m에 도달하면 출력
        if len(combination) == m:
            print(' '.join(map(str, combination)))
            return
        
        # start부터 n까지 숫자를 하나씩 선택
        for num in range(start, n + 1):
            combination.append(num) # 숫자를 추가하고
            backtrack(num + 1, combination) # 시작 숫자를 1 추가하여 오름차순으로 검증
            combination.pop() # 위에서 return 되었다면 해당 수열에서 마지막 pop 하고 for문 동작
        
    backtrack(1, []) # 조합 탐색 시작 -> 1부터 시작


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().rstrip().split())
    generate_combinations(n, m)

3.2 itertools 활용: 기구현된 라이브러리

# 다른 풀이
import sys
from itertools import combinations

def main():
    n, m = map(int, sys.stdin.readline().rstrip().split())
    
    results = None
    results = combinations(range(1, n + 1), m)
    
    for combination in results:
        print(' '.join(map(str, combination)))
    


if __name__ == "__main__":
    main()