[파이썬] 15649 N과 M (1) feat 띠용하다!

오늘은 백트래킹을 풀어보기로 했다

 

사실 dfs 가 적혀있어서 그래프를 마치고 하려 했는데 

 

dfs만으로도 풀 수 있는데 왜 묵히고 있었을까!라는 마음에 그냥 들어가 보기로 했다

 

문제는... 사실 for문으로 풀까 생각했다

 

근데 그러면 백트래킹이 아니라 브루트 포스가 아닌가! 

 

결국 for문을 적절하게 제어할만한 방법이 필요하다 

 

거기서 dfs를 쓴다는 것을 알게 되었다

 

사실문제 보고 답이 없어서 구글링을 하면서 수십 개의 답을 봤다

 

결국 메커니즘은 같았는데 이러하다 

 

 

1. 숫자 2개를 받아 dfs 시작 

 

2. 4, 4일 경우 1부터 시작해서 4까지 가면서 배열에 for숫자를 넣어준다

 

근데 여기서 for 숫자 하나에 각각 dfs를 걸어준다

예를 들어서 for i==1일 때 dfs를 걸어 다시 1부터 시작하게 한다

 

그럼 for 1일 때 dfs >> for1 있으니 for2에 dfs가 걸리고 

for1> 2 > 1, 2일 때 있으니 for3에서 dfs.. 반복한다

 

for 4면 우리가 목표로 하는 길이 값인 m에 도달한다 길이 값에 도착했을 때

배열에서 마지막 값을 빼야 하기 때문에 dfs 구문 다음에 pop도 걸어준다

 

3. 그러면 목표 도달했으니 ary를 출력하고 for4값의 dfs> pop [1, 2, 3]

 

for3값으로 넘어왔으니 다시 pop[1, 2]

 

4. i는 dfs3일 때 4가 되고 다시 4를 넣고 [1, 2, 4]dfs, dfs 4>3일 때 3이 없으니 3을 넣고 dfs[1, 2, 4, 3]

 

5. 그럼 배열 길이가 4니 다시 출력하고 뒤로, 이번에는 dfs3>i4이니 pop하고 끝 [1, 2, 4]

 

6. df3>i3으로 다시 돌아와 pop [1, 2] 

 

7. 또 똑같이 더 뒤로 돌아가서 2>2 값도 pop [1]

 

8. 그럼 dfs2>i3이니 3부터 시작.. 위의 차례를 반복

 

 

def back():     if len(ans) == m:         print(*ans)         return     for i in range(1, n+1):         if i not in ans:             ans.append(i)             back()             ans.pop() n, m = map(int,input().split()) ans = [] back()

 

 

참 생각하는 거지만 이런 이론을 생각하려면 머리가 얼마나 좋아야 하는 걸까..

 

dp보다는 쉽게 이해했지만 그래도 세상 참 머리가 좋은 사람이 많다고 느껴지는 문제 풀이었다