백트래킹(BackTracking)

🌱 백트래킹

백트래킹(BackTracking)은 다른 알고리즘 정도는 아니라 일종의 기법, 전략입니다. 백트래킹(Backtracking, 퇴각 검색)은 일종의 해를 찾기 위해 재귀적으로 문제를 풀어나가다가 제약 조건에 위배가 된다면 제외 표시를 하고 다음 단계로 넘어가는 방법입니다.

구현하는 방법

결론적으로, 백트래킹 기법은 제약 조건을 만족하는 경우를 탐색하기 때문에 DFS와 BFS와 같은 완전 탐색 기법으로 구현이 가능합니다.

그러나, 특성상 제약조건에 만족하지 않으면 다시 이전 노드로 돌아와야 하기 때문에 BFS보다는 DFS로 구현하기 편합니다.물론 시간이 부족한 경우엔 BFS로 풀어야합니다. 

그리고 만약 제약조건에 만족하지 않는 경우 다른 루트로 돌아가야 합니다. 이때, 조건에 만족하는지 확인하는 것을  Promising이라하고 조건에 만족하지 않아 다른 루트로 가는 것을 가치치기(Pruning)이라고 합니다.

따라서, DFS를 통해 모든 노드를 탐색하면서 제약 조건에 만족하지 않는 경우 가지치기(Pruning)로 제외시키면 됩니다.

백 트래킹 문제 풀이(N-Queen)

다음 N-Queen 문제를 봅시다.

 

NXN 크기의 체스 보드 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

• 입력 : 첫째 줄에 N이 주어진다. (1 <= N < 15) ex) `8`
• 출력 : 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. ex) `92`

여기서 Queen을 놓지 못하는 경우는 대각선의 경우와 바로 위에 퀸이 있는 경우입니다.

 

먼저, 이번 문제에서는 굳이 이차원 배열까지 만들 필요가 없습니다. 해당 행(Row)의 퀸을 놓을 수 있는지를 판별하면 되기 때문입니다.

제약조건인 대각선과 바로 위에 있지 않으면 다음 행(row)으로 넘어가도 되고 있으면 다음 열로 탐색하는 코드를 작성하면 됩니다.

 

다음 그림 처럼, 퀸을 첫번째 행의 첫번째 열에 둔다고 가정해봅시다. 첫번째 열은 그냥 둘 수 있습니다.

 

다음 행의 경우는 어떨까요?

다음 행의 경우 같은 행에 퀸을 둔다고 가정하면 바로 위에 퀸이 있기 때문에 놓을 수 없을 것입니다. 그러므로 다음 열에 두어야 가능합니다.

이런식으로 작성하다보면 언젠간 X가 N까지 도착하게 됩니다. 이럴 때 경우의 수가 하나 추가됩니다.

그렇지 않은 경우에는 다시 재귀적으로 진행하게 됩니다.

 

def check(x):
    """
    x번째 행에 QUEEN을 두어도 괜찮은지 확인
    """
    # 각 이전 행들(i)과 현재행(x) 하나씩 확인
    for i in range(x):
        # 위쪽 행에 다른 퀸이 놓여 있으면 False 반환
        if row[x] == row[i]:
            return False
        # 대각선 방향 겹치는게 있다면 False 반환
        if abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(x):
    """
    `x`번째 행에 대해 처리 (첫번쨰 행 부터)
    - n번째 행 까지 모두 퀸을 놓을 수 있는 경우엔 `result += 1`
        - 모든 행에 대해 계산

    - x 번째의 행의 각 열(0 ~ N-1)에 퀸을 둔다고 가정한다. 
        - 해당 위치에 Queen을 두어도 괜찮으면 다음 행으로 넘아간다.

    """
    global result
    if x == n:
        result += 1
    else:
        for i in range(n):
            # 우선, Queen을 두었다고 가정
            row[x] = i
            # 해당 위치에 퀸을 두어도 괜찮은지 `check(x)`
            if check(x):
                dfs(x + 1) # 놓을 수 있다면 다음행으로

n = int(input())
row = [0] * n # 행의 대한 정보
result = 0
dfs(0)
print(result)

 

---

🚀 암호만들기 문제

[백준1759] - 암호만들기↗

 

해당 문제는 몇가지 조건에 해당하는 암호들을 만드는 문제입니다.

• 두 개 이상의 자음과 한개 이상의 모음으로 이루어진다.
• 문자가 사전식 순서대로 만들어져 있어야 한다.
• 중복을 허용하지 않는다.

 

먼저, 4글자의 암호를 만들려면 문자열을 정렬해야합니다. 이유는 사전식 순서대로 만들어야 하기 때문입니다.

그리고 1개 이상의 자음이 포함되어야 한다고 했기 때문에 `vowels`라는 자음 리스트를 만들어 줍니다.

vowels = ['a', 'e', 'i', 'o', 'u'] # 최소 한개의 모음
l, c = map(int, input().split(" "))
words = [i for i in input().split(" ")]
words.sort()

 

실제로 배열에 문자를 넣고 앞 문자가 현재 문자보다 작은 경우에만 암호를 만들 수 있도록 코드를 작성해야 합니다.

첫문자는 사전식 순서로 가장 앞에 있는 문자 3개만 가능합니다. 만약 `t`가 가장 앞에 나오면  `tw`다음으로 만들 수 있는 문자가 없기 때문입니다. 

result = []
for i in range(c - l + 1):
    a = [words[i]]
    bt(a) # [a] , [c],  [i]

 

이번엔 백트래킹을 구현하려고 합니다.

만약 문자열이 4개인 암호가 다 채워졌을 경우엔 해당 문자열(`result`)을 출력하고 그 전까지는 문자를 서로 비교하면서 채울 예정입니다.

def bt(result):
    if len(result) == l:
        if check(result):
            print("".join(result))
            return
        
    for i in range(len(result), c):
        if result[-1] < words[i]:
            result.append(words[i])
            bt(result)
            result.pop()

 

백트래킹

그 다음, `check` 함수를 통해 문자열에 모음이 1개이상인지 자음이 2개이상인지를 확인해야합니다.

만약 암호에 `a`나 `i`가 들어가 있지 않으면 다시 돌아가 다음 문자로 확인하게 되는 구조입니다.

def check(result):
    v, c = 0, 0
    for i in result:
        if i in vowels:
            v += 1
        else:
            c += 1
    
    if v >= 1 and c >= 2:
        return True
    else:
        return False

 

---

☕️ 마치며

오늘도 저의 포스트를 읽어주셔서 감사합니다. 

설명이 부족하거나 이해하기 어렵거나 잘못된 부분이 있으면 부담없이 댓글로 남겨주시면 감사하겠습니다.