[백준/python]15649번 N과 M (1), 15650번 N과 M(2) - backtracking

N과 M 문제를 통해 백트래킹을 익혀보자.

백트래킹에서 가장 중요한 전략은 가지치기이다. 백트래킹은 기본적으로 재귀 함수로 구현된 DFS의 구조이다. 재귀를 반복하며 조건과 맞지 않는 케이스를 잘 처리하는 것이 중요하다.

15649번 N과 M (1)

코드

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

ans=0   

def DFS(ans):
    global arr
    
    if ans==M:
        print(' '.join(map(str, arr)))
        return
        
        
        
    for i in range(1, N+1):
        if i not in arr:
            arr.append(i)
            DFS(ans+1)
            arr.pop()

DFS(0)

구현

arr 배열을 전역 변수로 사용한다.

1. 1부터 N까지의 숫자를 반복문을 통해 배열에 넣고 DFS를 돌린다.
2. 이후에 다시 pop하는 과정을 통해 DFS 실행 이전으로 되돌려 준다. 이 부분이 백트래킹의 핵심이다.
3. arr에 들어간 원소의 개수가 M이 되면 arr를 바로 print해준다. 처음에는 이렇게 재귀함수의 input에 원소의 개수를 담아서 전달했다. 하지만 변수를 사용하지 않고 배열의 길이를 활용하여 풀 수 있다.

수정된 코드

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

def DFS():
    global arr
    
    if len(arr)==M:
        print(' '.join(map(str, arr)))
        
        
        
    for i in range(1, N+1):
        if i not in arr:
            arr.append(i)
            DFS()
            arr.pop()

DFS()

---

15650번 N과 M (2)

위의 문제와 다르게 중복이 불가능한 수열이다. 즉 위의 문제는 1부터 N까지의 숫자에서 순열을 뽑는 문제, 해당 문제는 조합를 뽑는 문제이다.

15649번 문제에서 ans를 넘겨주는 풀이에서 착안하여 이번에는 재귀함수에 반복문에서 뽑았던 마지막 인덱스를 변수로 넘겨준다. 이를 통해 앞에서 지나온 숫자들은 다시 반복문에서 실행되지 않게 된다.

코드

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

def DFS(idx):
    global arr
    
    if idx == N+1:
        return 
    
    if len(arr)==M:
        print(' '.join(map(str, arr)))
        return
        
        
        
    for i in range(idx, N+1):
        if i not in arr:
            arr.append(i)
            DFS(i)
            arr.pop()

DFS(1)