[알고리즘] 9. 백트래킹

KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.

9주차. 백트래킹을 이용한 해의 탐색과 실제

---

 

9주차. 백트래킹을 이용한 해의 탐색과 실제

 

1.  백트래킹과 효율적 해 탐색

1) 백트래킹

(1) 백트래킹 이란?

• 가능한 모든 해를 탐색하되, 조건에 어긋나는 경우 이전으로 돌아가는 방법 (-> 이부분이 Brute-Force와 차이)
• 어떤 지점이 해의 조건에 위배되었을 경우, 해당 지점보다 깊은 해는
• 문제 해결에 있어, 일반적인 완전 탐색 알고리즘보다 높은 성능을 기대할 수 있다. 
• Tree에서 DFS와  관련있다.

 

(2) 문제 예시

(순열) 한 줄로 서기 -> 앞에 선 사람은 뒤에 설 수 없으므로 이전으로 돌아감. 

# Week 9
# Line-up (Back-Tracking)

member = ['R', 'G', 'Le', 'Li']
line = []
for i in range(0, len(member)):
    line.append('')
    

def line_up(num):
    # 중복 확인
    if check(num) == True:
        # 줄 다 선 경우
        if num == len(member):
            print(line)
        # 모든 멤버 줄 맨 뒤에 세워보기
        else:
            for mem in member:
                line[num] = mem
                line_up(num+1)

# 중복 확인
def check(num):
	# 맨 앞
    if num == 0:
        return True
    # 줄에 선 사람들과 추가할 사람 비교
    target = line[num-1]
    for mem in line[0:(num-1)]:
        if mem == target:
            return False
    return True
    
line_up(0)

'''
Output
['R', 'G', 'Le', 'Li']
['R', 'G', 'Li', 'Le']
['R', 'Le', 'G', 'Li']
['R', 'Le', 'Li', 'G']
['R', 'Li', 'G', 'Le']
['R', 'Li', 'Le', 'G']
['G', 'R', 'Le', 'Li']
['G', 'R', 'Li', 'Le']
['G', 'Le', 'R', 'Li']
['G', 'Le', 'Li', 'R']
['G', 'Li', 'R', 'Le']
['G', 'Li', 'Le', 'R']
['Le', 'R', 'G', 'Li']
['Le', 'R', 'Li', 'G']
['Le', 'G', 'R', 'Li']
['Le', 'G', 'Li', 'R']
['Le', 'Li', 'R', 'G']
['Le', 'Li', 'G', 'R']
['Li', 'R', 'G', 'Le']
['Li', 'R', 'Le', 'G']
['Li', 'G', 'R', 'Le']
['Li', 'G', 'Le', 'R']
['Li', 'Le', 'R', 'G']
['Li', 'Le', 'G', 'R']
'''

# Week 9
# Line-up

from itertools import permutations

member = ['R', 'G', 'Le', 'Li']

for p in permutations(member, 4):
    print(p)
    
'''
Output

('R', 'G', 'Le', 'Li')
('R', 'G', 'Li', 'Le')
('R', 'Le', 'G', 'Li')
('R', 'Le', 'Li', 'G')
('R', 'Li', 'G', 'Le')
('R', 'Li', 'Le', 'G')
('G', 'R', 'Le', 'Li')
('G', 'R', 'Li', 'Le')
('G', 'Le', 'R', 'Li')
('G', 'Le', 'Li', 'R')
('G', 'Li', 'R', 'Le')
('G', 'Li', 'Le', 'R')
('Le', 'R', 'G', 'Li')
('Le', 'R', 'Li', 'G')
('Le', 'G', 'R', 'Li')
('Le', 'G', 'Li', 'R')
('Le', 'Li', 'R', 'G')
('Le', 'Li', 'G', 'R')
('Li', 'R', 'G', 'Le')
('Li', 'R', 'Le', 'G')
('Li', 'G', 'R', 'Le')
('Li', 'G', 'Le', 'R')
('Li', 'Le', 'R', 'G')
('Li', 'Le', 'G', 'R')
'''

 

2.  N-Queen 문제와 백트래킹

1) 문제 

백준 3344 번 N-Queen

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

 

2) 풀이

백준 3344는 가능한 한 경우만 출력하는 문제이고

아래는 모든 가능한 경우를 출력하는 예제이다. 

N = 4
ans = []
for i in range(0, N):
    ans.append(-1)

def queen(num):
    if check(num) == True:
        if num == N:
            print(ans)
        else:
            for j in range(0, N):
                ans[num] = j
                queen(num+1)

def check(num):
    for k in range(0, num-1):
        if ans[num-1] == ans[k]:
            return False
        elif abs(ans[num-1] - ans[k]) == (num-1-k):
            return False
    return True

queen(0)

# output
# [1, 3, 0, 2]
# [2, 0, 3, 1]

 

 

3.  조합에서의 백트래킹

1) 문제

백준 2798 블랙잭

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

2) 코드 및 풀이

가진 카드 중 합이 21이 되는 조합 찾기

cards = [3,7,9,5,1,8,4]
target = 21

def black_jack(num, choose):
    if check(choose) == -1:
        if num < len(cards):
            black_jack(num+1, choose)
            black_jack(num+1, (choose+[cards[num]]))
    elif check(choose) == 0:
        print(choose)


def check(choose):
    if sum(choose) > target:
        return 1
    elif sum(choose) == target:
        return 0
    else:
        return -1

black_jack(0, list())

# Output
'''
[9, 8, 4]
[7, 5, 1, 8]
[7, 9, 1, 4]
[7, 9, 5]
[3, 5, 1, 8, 4]
[3, 9, 1, 8]
[3, 9, 5, 4]
'''

 

N개로 만들 수 있는 모든 조합은 2^N 개이다.

조합을 구성하는 과정에서 합이 21이 넘으면 무의미하다.

 

 

4. Python에서 순열과 조합

1) 순열 Permutation

n개중 r개를 뽑아 순서를 정해 나열하는 모든 경우의 수.  nPr 로 표시

Python에서는 itertools.permutations(리스트, r)   이렇게 사용

# Week 9
# Permutations

from itertools import permutations

lst = ['A', 'B', 'C']

for p in permutations(lst, 2):
    print(p)
    
'''
Output
('A', 'B')
('A', 'C')
('B', 'A')
('B', 'C')
('C', 'A')
('C', 'B')
'''

 

2) 조합 Combination

순열과 마찬가지로 n개중 r개를 뽑아 나열한 집합인데, 다른 점은 순서가 바뀌어도 원소가 동일하면 동일한 것으로 취급한다.

 

# Week 9
# Combinations

from itertools import combinations

lst = ['A', 'B', 'C']

for c in combinations(lst, 2):
    print(c)
   
'''
Output
('A', 'B')
('A', 'C')
('B', 'C')
'''

조합에서는 (A, B) 와 (B, A) 를 동일한 것으로 보기 때문에 (B, A), (C, A), (C, B) 는 제외되었다.