Baekjoon 백준 알고리즘 - N과 M ( 15649 )

1. 문제 소개

• 백트래킹 알고리즘 유형 문제에 해당한다.

 

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

2. 코드

STACK = []
VISIT = []
N,M=0,0

def input_test_case():
	input_str= input().split(" ")
	N,M = int(input_str[0]),int(input_str[1])

	return N,M
# N 4,2  / 1,2,3,4 
def combinations(NUM,CNT):
	global VISIT,STACK,N,M
	if CNT==M:
		parsed_stack = map(lambda x: str(x),STACK)
		print(" ".join(parsed_stack))
		
		return 0

	for i in range(1,N+1):
		if NUM == i or VISIT[(i-1)]:
			continue

		STACK.append(i)
		VISIT[i-1]=True
		combinations(i,CNT+1)
		STACK.pop()
		VISIT[(i-1)]=False

def solution():
	global VISIT,STACK,N,M 
	N,M=input_test_case()
	
	VISIT = [False]* N
	combinations(0, 0)
	#print(f'N :{N} \t M : {M}')
	
def main():
	solution()
	

main()

3. 코멘트

• 백트래킹 쉽게 요약하면 탐색과정에 더 이상의 해가 없는 경우를 IF 조건으로 만들어 다음 탐색으로 넘어가는 알고리즘이다.
• combinations()에서 DFS 로 탐색을하고, 백트래킹 탈출 조건을 수열의 길이가 M 일때로 잡고, 정답을 출력하도록 했다.