[BaekJoon] 백준 15652번 : N과 M (4)

15652번 : N과 M (4)

백트래킹 알고리즘을 사용하면 되는 문제이다.

백트래킹이란 DFS, BFS 로 탐색을 하면서 내가 원하는 조건에 맞지 않는 노드에 방문했을경우 부모노드로 되돌아가는 알고리즘이다.

n = 3, m = 3 인 경우로 예를 들어보면 만약 2에서 1로 가는 경우 조건에 맞지 않기 때문에 바로 부모로 돌아간다.

---

import sys


def DFS(index):
	global n, m, data, stack

	if len(stack) == m:
		print(*stack)
		return

	for i in range(index, n):
		if stack and data[i] < stack[-1]:
			continue
		stack.append(data[i])
		DFS(0)
		stack.pop()


n, m = map(int, sys.stdin.readline().rsplit())
data = [i for i in range(1, n + 1)]
stack = []
DFS(0)

추가로 리스트를 원소만 출력하고 싶은 경우 print(*list) 를 사용하면 된다.

---

import sys
from itertools import combinations_with_replacement


n, m = map(int, sys.stdin.readline().rsplit())
res = combinations_with_replacement(range(1, n+1), m)

for i in res:
	print(*i)

또 combination_with_replacement 를 사용하면 같은 수를 여러번 고른 조합을 만들어준다.