Problem Link

처음 보는 백트래킹 문제라서
개념부터 공부 할 필요가 있었다.

백트래킹

모든 경우의 수를 확인할 때

• for로는 확인 불가한 경우 (깊이가 달라질 때)
  예를 들어, N개의 숫자 중 M개의 숫자를 골라야 할 때

def a(num)
	if num == M
    	return
    for 1부터 N까지
    	결과값 추가 + 방문여부 체크
    a(num + 1)

의 방식으로 구현 가능하다는 것 ...?

• 재귀함수는 트리 구조로 이해하는 것이 편하다
• 백트래킹 문제는 N이 작음
• 재귀함수 쓸 때, 종료 시점 잊지 않기

대충 강의에서는 그렇게 설명하는데
직접 풀어보기로 했다.

---

N과 M (1)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

1부터 N까지 for 돌면서 숫자 중 하나 선택
다시 1부터 N까지 숫자 중 하나 선택, 이미 선택한 값이 아니어야 함
선택한 숫자의 개수가 M에 도달하면 print

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ans = []
visit = [False] * (N + 1)

여기서부터는 backtracking 기본 패턴이므로 몸에 익히기

def recur(num):
    if num == M:
        print(' '.join(map(str, ans)))
        return
    for i in range(1, N+1):
    	if visit[i] == False:
            visit[i] = True
            ans.append(i)
            recur(num + 1)
            visit[i] = False
            ans.pop()
recur(0)

위 코드에서,

visit[i] = False
ans.pop()

부분이 빠지면, [1,2] 에서 멈추지 않고 [1,2,3] 까지 출력하게 되기 때문에 반드시 방문 여부인 visit을 False로 변경하고 pop() 함수를 사용해 제거해 주도록 하자.

sys.stdin.readline이랑 백트래킹 기본 구조는 빨리 손에 익히자