[백준] 15469 - N과 M (1)

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

 

알고리즘

백트래킹 

 

풀이  <1> : 순열 

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

중복없이 -> 순열 사용 

1~N까지 수를 담은 배열을 만든 뒤, 그 배열에서 자연수 M개를 뽑음

 

from itertools import permutations

N, M = map(int, input().split())

arr = []
for i in range(N):
    arr.append(i+1)

for combi in permutations(arr, M):
    for i in combi:
        print(i, end=" ")
    print()

 

그런데.. 

 

이 문제는 백트래킹 문제였다...

백트래킹 그게 뭔데...

백트래킹 그거 어떻게 하는건데...

 

백트래킹이란? 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 알고리즘이다. 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기라고도 한다.

 

풀이 <2> : 백트래킹 

이 알고리즘은 재귀로 해결할 수 있다.

1 ~ N 까지 숫자 중에서 정답 배열 ans에 없다면 추가해주고 아니라면 다음 수로 넘아간다. 

배열의 길이가 M과 같다면 정답을 출력해준다.

 

N=3, M=2로 예시를 들자면,

1~3까지 숫자 중에서 중복없이 2개씩 뽑는 문제이다.

# N과 M (1) 백트래킹 

N, M = map(int, input().split())
ans = []

def back():
    if len(ans) == M: # 배열의 길이
        for i in ans:
            print(i, end=" ")
        print()
    
    for i in range(1, N+1):
        if i not in ans: # 중복 확인 
            ans.append(i)
            back() # 재귀 
            ans.pop() # 마지막 요소를 제거하여 되돌아오기 

back()

 

첫번째 재귀로 ans = [1], 두번째 재귀로 ans = [1, 2] => 길이가 M에 도달했기 때문에 1 2 출력

ans.pop()으로 2를 제거하여 ans = [1], 재귀로 ans = [1, 3] => 길이가 M에 도달했기 때문에 1 3 출력 

ans.pop()으로 3제거, 그 다음으로 1제거, ans = [] 

이 과정을 N까지 반복 시행한다.

 

그러나... 

 

위가 순열, 아래가 백트래킹으로 푼 결과인데 결과로만 보면 파이썬 내장 함수인 순열을 활용해서 푸는게 나았다.