완전탐색 - 백트래킹

백트래킹이란? 🤔

완전 탐색을 하는 도중, 현재 탐색이 무의미한 경우 되돌아가는 알고리즘

• DFS(Depth First Search) 깊이 우선 탐색
• BFS(Breadth First Search) 너비 우선 탐색

구현 과정 📌

def 재귀함수(x) :
  if 정답이라면? : 
	정답 출력 또는 저장
  else : 정답이 아니라면?
    for 뻗을 수 있는 모든 자식 노드에 대해서 : 
      if 정답에 유망하다면 :
      	자식노드로 이동
        재귀함수(x+1)
	부모노드로 이동

백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising)한다. 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버린다.(Pruning)

기본 문제 📁

🪄 N-Queen

크기가 N X N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제

# 겹치는 라인에 퀸이 있는지 체크(Promising)
def promising(x):
    for i in range(x):
        # 겹치는 라인에 퀸이 있으면 가지치기(Pruning)
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True

# 트리 구조 기반으로 DFS를 실행
def dfs(x):
    global result

    # 배치한 퀸의 개수가 N과 같아지면 result 증가
    if x == N:
        result += 1

    else:
        for i in range(N):
            row[x] = i
            # 만약 나와 겹치는 라인에 퀸이 없다면, 그 다음줄에 재귀적으로 DFS를 실행
            if promising(x):
                dfs(x + 1)


N = int(input())
row = [0] * N
result = 0
dfs(0)
print(result)

백트래킹 대부분의 문제는 시간초과로 인해 파이썬으로 풀기 부적합하다고 한다.
왜 그런지는 모르겠다.🤔

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])

그래서 이렇게 입력하면 통과 할 수 있다. 😎

🪄 N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제

풀이 1. itertools 모듈의 permutations를 사용하여 풀기
풀이 2. 재귀 함수로 구현하기

def progression(x):
    # 리스트의 길이가 m이 된다면 출력
    if len(ans) == m:
        print(*ans)
        return  # 더 이상 탐색하지 않도록 가지치기

    for i in range(1, n+1):
        if i not in ans:
            ans.append(i)  # 아직 리스트의 길이가 m이 아니고, 리스트 안에 i 값이 없으므로 넣어준다
            progression(i + 1)  # 재귀적으로 progression 함수를 실행한다
            ans.pop()  # i 값을 넣어줬을 때의 탐색이 끝났으므로 다시 값을 빼준다 (스택 형식)

n, m = map(int, input().split())
ans = []
progression(1)

🪄 스타트와 링크

모든 (i, j)에 대한 능력치가 주어졌을 때 두 팀 능력치 차이의 최솟값을 구하는 문제

풀이 1. itertools 모듈의 combinations를 사용하여 풀기
풀이 2. 재귀 함수로 구현하기

def playerAbility(idx, num):
    global res

    # 팀을 모두 구했으면 점수를 계산한다
    if num == n // 2:
        aTeam, bTeam = 0, 0
        for i in range(n):
            for j in range(i+1, n):
                # 두 선수가 같은 팀인지 확인하고, 같은 팀이면 점수를 부여한다
                if team[i] == team[j]:
                    if team[i] == 0: aTeam += arr[i][j] + arr[j][i]
                    else: bTeam += arr[i][j] + arr[j][i]
        # 팀 점수의 차이가 res보다 작은 지 확인한다
        res = min(res, abs(aTeam - bTeam))
        return  # 탐색종료

    # 팀을 정하는 for문
    for i in range(idx+1, n):
        team[i] = 1
        # 재귀함수를 통해서, i가 B팀에 속한 모든 경우의 수를 확인한다
        playerAbility(i, num + 1)
        # 그 후에 i를 A팀으로 바꾼다
        team[i] = 0


n = int(input())
arr = [[*map(int, input().split())] for _ in range(n)]
res = float('inf') # 무한대
team = [0] * n
playerAbility(0, 0)
print(res)

🪄 부등호

k개의 부등호 순서를 만족하는 (k+1) 자리의 정수 중에서 최댓값과 최솟값을 찾는 문제

풀이 1. itertools 모듈의 permutations를 사용하여 풀기
풀이 2. 재귀 함수로 구현하기

def inequalitySign(idx):
    global minAns, maxAns
    # n값과 같아졌으면, 조건문으로 비교해서 minAns나 maxAns에 넣어준다
    if idx == n:
        # map()으로 str로 변경해서 join으로 한 문자열로 만든다
        val = ''.join(map(str, ans))
        if minAns[0] > int(val): minAns = [int(val), val]
        if maxAns[0] < int(val): maxAns = [int(val), val]
        return  # 탐색종료
    for i in range(10):
        if i not in ans:
            # 부등호대로 값을 넣을 수 있는 지 확인
            if (s[idx] == '<' and ans[-1] < i) or (s[idx] == '>' and ans[-1] > i):
                ans.append(i)
                inequalitySign(idx + 1)
                ans.pop()  # 탐색이 끝났으면 제거


n = int(input())
s = input().split()
ans = []
minAns = [float('inf'), '']
maxAns = [0, '']
# 재귀적으로 inequalitySign 함수를 실행한다
for i in range(10):
    ans.append(i)
    inequalitySign(0)
    ans.pop()
print(maxAns[1])
print(minAns[1])