[Python]백트래킹 백준 15649

   문제

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

백트래킹과 브루트포스는 굉장히 비슷해보인다

차이점을 찾아봤다.

백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 

기법입니다. 반드시 DFS만으로 가능한 게 아니고 BFS 등으로도 가능하지만 일반적으로

 DFS와 연관이 깊기는 합니다.브루트 포스는 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 

경우의 수를 다 대입해보는 것이면 브루트 포스입니다. 

어떤 종류의 문제에서 어떤 방법을 쓰더라도요.

DFS는 여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로

 돌아가야만 DFS입니다.순서의 여부가 중요한게 아닐까?

어쨋든 문제로 들어가 보면 재귀를 잘 활용한다면 백트래킹 브루트포스 DFS등을 풀기 

쉬울것이다.

n, m = map(int, input().split())    # n까지 m개
check=[0 for _ in range(n+1)]
result=[0 for _ in range(m)]
 
def sequence(index,n,m):
    if index==m:
        for i in range(m):
            print(result[i], end=' ')
        print()
        return
 
    for i in range(1,n+1):
        if check[i]==1:#이전에 썻다면
            continue
        result[index]=i #해당위치에 넣어줌
        check[i]=1  #들어간거 체크표시
        sequence(index+1,n,m)
        check[i]=0 #다음수로 넘어가기전에 초기화
 
 
sequence(0,n,m)

재귀 잘쓰는 사람보면 멋있어 보인다.

제일 처음 프로그래밍을 배울때 재귀를 웬만하면 사용하지 말라는 말을 들어서 재귀를 사

용하지 않았는데 알고리즘을 구현하는데 있어서는 필수역량이 아닌가 생각이 든다.