[알고리즘] Backtracking

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.

이를 활용해 의사결정을 하는 예로는, 미연시나 역전재판같은 롤 플레잉 게임에서, 하나의 선택지마다 다른 결과값을 불러올 수 있으며, 이를 뒤로가기 하면 다른 방식으로 탐색할 수 있다.

백트래킹을 활용한 알고리즘 함수에 포함할 내용은 다음과 같다. 아래는 전역 변수로 설정할 변수이다.

n, m 입력값

array : 수열을 담을 빈 배열

visited / issued : 쓰였는지 확인하는 true/false 배열. 이 배열은 위 수열의 개수만큼 필요하고, 초기값은 0 (false)로 설정한다.

함수의 형태는 1) 종료조건과 만족 시 값 리턴 2) 아니면 원하는 조건의 함수 호출한다.

예제로 백준의 N과 M 문제를 풀어보았다.

15649 : N 과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

우선 이 문제는 백트래킹을 이해하기 위해 아래 링크한 유튜브 강의의 코드를 그대로 따라한 코드이다. 자세한 설명이 필요하다면 아래 링크를 참조하라.

dfs(n, lst) 는 현재까지 선택한 개수 n과 선택한 숫자 리스트 lst를 매개변수로 받는다.

종료 조건을 만나면 lst를 정답 리스트 (ans)에 저장하고 탐색을 종료한다.

그렇지 않다면 1 ~ N 까지의 숫자를 검사하며 사용되지 않은 숫자만 선택하여 다음 단계로 재귀 호출한다. if v[j] == 0 으로 숫자가 사용되었는지 검사 후, v[j] =1 로 방문한 숫자를 체크한다. 탐색이 끝나면 다시 v[j] = 0 로 초기화하여 새로운 조합을 찾을 수 있도록 한다.

list.append(j)를 사용하면 원본 리스트가 변경되므로 재귀 호출마다 lst+[j]로 새로운 리스트를 만들어 원본을 유지하면서 새로운 숫자를 추가한다.

def dfs(n, lst):
    #종료 조건 n에 따라 값 리턴, 정답처리
    if n == M:      #M개를 고른 수열을 완성
        ans.append(lst)
        return
    
    #조건문 함수
    for j in range(1, N+1): # N의 갯수만큼 검사
        if v[j]==0:
            v[j]=1
            dfs(n+1, lst+[j])
            v[j]=0
        
N, M = map(int, input().split())
ans = []
v = [0]*(N+1)

dfs(0, [])
for lst in ans :
    print(*lst)

15650 : N 과 M (2)

위 문제에서 아래 조건이 추가되었다.

조건 2 : 고른 수열은 오름차순이어야 한다.

조건에 따라 2가지 코드가 추가되었다.

1. 중복 조합 방지 조건 추가 : if list and j < list[-1] : continue

기존 코드의 출력을 보면 숫자가 끝까지 탐색을 마치고 돌아가는 과정에서 마지막 숫자보다 작은 조합의 숫자가 중복으로 출력된다는 것을 볼 수 있다. 이 경우, 마지막으로 list 에 추가된 조합의 숫자가 추가하려는 j 보다 큰 경우, 건너뛴다는 조건을 추가하였다.

여기서 이해가 안되었던 부분은 list 조건이 필요한 이유였다. 이 조건이 없으면, index error가 발생한다. 그 이유는 list가 빈 비열일때 생기는 것으로, list 조건이 추가되면서 배열에 숫자있는 경우만 True를 리턴하며 그 이후 and 조건을 탐색하고, 만약 배열이 비어있다면 False 이기 때문에 and 조건과 continue가 무시되고 이후 함수로 진행된다.

1. 출력 순서 정렬 : sorted(ar)

def dfs (a, list):
    if a == m :
        ar.append(list)
        return
    for j in range(1, n+1):
        if list and j < list[-1]:
            continue
        if v[j] == 0:
            v[j] =1
            dfs(a+1, list+[j]) 
            v[j] =0

n, m = map(int, input().split())
ar = []
v = [0]*(n+1)

dfs (0, [])
for ar in ar :
    ans = sorted(ar)
    print(*ans)

추가로 처음에는 위의 if 조건문을 아래 조건문 속의 v[j] =1 이 부분 이후에 넣었으나, 반례 발생으로 실패했다. 반례의 예시는 다음과 같이 출력된다. 디버깅을 실행한 결과 백트래킹 과정에서 마지막 입력값이 4로 고정되어, 그 이후 2, 3 등의 숫자가 리스트에 추가되지 않는다. If 문을 visited를 검증하기 전에 확인하여, 이미 방문한 숫자가 리스트에 추가되기 전에 중복을 방지하도록 수정하였다.

Input : 4 3
Expected Output : 
1 2 3
1 2 4
1 3 4
2 3 4

My Output : 
1 2 3
1 2 4
1 3 4

Debugging : 
[1, 3] 2
[1, 4] 3
[4] 1

15651 : N 과 M (3)

조건이 다음과 같이 바뀌었다. 수열 내에서 같은 수의 중복을 허용한다.

조건 1 : 1부터 N까지 자연수 중에서 M개를 고른 수열

조건 2 : 같은 수를 여러 번 골라도 된다.

이 문제는 쉽게 풀 수 있었다. visited로 중복을 검사하는 부분을 제외한다.

def dfs (a, list):
    if a == m:
        ar.append(list)
        return
    
    for j in range(1, n+1):
        dfs(a+1, list+[j])

n, m = map(int, input().split())
ar = []

dfs(0, [])
for ar in ar :
    print(*ar)

15652 : N과 M (4)

3에서 조건 1개 추가.

조건 3 : 고른 수열은 비내림차순이어야 한다.

비내림차순의 정의는 다음과 같다. 내림차순은 점점 감소하는 수열이고 비내림차순은 점점 증가하는 수열이다. 오히려 비내림차순은 오름차순과 비슷한데, 차이점은 오름차순은 인접한 두 수가 같을 수도 있는지 여부를 명확하게 알려주지 않지만 비내림차순은 같을 수도 있음을 명확히 해준 것이라고 볼 수 있다. ( 이 정의로만 보면 헷갈린다 )

비내림차순을 이해하려면 예제 코드를 보면 알 수 있다. 요구하는 코드에서는 [ 3, 4 ] 이후에 [ 4, 4 ] 가 와야 한다. 하지만 조건문을 추가하지 않은 이전 문제의 코드에서는 [ 3, 4 ] 이후 다시 [ 4, 1 ] 부터 탐색을 시작한다. 이 경우 이전과 동일한 조건문을 추가해주면, 리스트의 마지막 값이 j 보다 작은 경우를 제외하고 탐색할 수 있다.

Input : 4 2 
Expected Output : 
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

15651 실행 시, output :
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

def dfs (a, list):
    if a == m:
        ar.append(list)
        return
    
    for j in range (1, n+1):
        if list and j < list[-1]:
            continue
        dfs (a+1, list+[j])

n, m = map(int, input().split())
ar = []

dfs (0, [])
for ar in ar :
    print(*ar)

---

[바킹독의 실전 알고리즘] 0x0C강 - 백트래킹

 

[백준문제집 백트래킹 #01] 15649. N과 M (1) (백준, 파이썬)