💻 [코테07] 12장 백트래킹

12장. 백트래킹

12-1. 백트래킹과 백트래킹 알고리즘 개념

1) 백트래킹(backtracking)이란?

• 어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것

2) 백트래킹 알고리즘이란?

• 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘

3) 유망 함수란?

• 백트래킹의 핵심 : 해가 될 가능성을 판단하는 것
• 유망 함수 : 해가 될 가능성을 판단하기 위해 정의한 함수

  🎫 백트래킹 알고리즘 과정
  1) 유효한 해의 집합 정의
  2) 위 단계에서 정의한 집한을 그래프로 표현
  3) 유망 함수 정의
  4) 백트래킹 알고리즘을 활용하여 해 찾기

12-2. 몸풀기 문제

• 문제47_1부터 N까지 숫자 중 합이 10이 되는 조합 구하기

def solution(N):
    results = []
    
    def backtrack(sum, selected_nums, start):
        if sum == 10:
            results.append(selected_nums)
            return
        
        for i in range(start, N+1):
            if sum + i <= 10:
                backtrack(sum+i, selected_nums+[i], i+1)
    
    backtrack(0, [], 1)
    return results

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution(5)) # 반환값 : [[1, 2, 3, 4], [1, 4, 5], [2, 3, 5]]
print(solution(2)) # 반환값 : []
print(solution(7)) # 반환값 : [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5], [3, 7], [4, 6]]

• 문제48_스도쿠 퍼즐

def solution(board):
    def is_valid(num, row, col):
        return not(in_row(num, row) or in_col(num, col) or in_box(num, row, col))
    
    def in_row(num, row):
        return num in board[row]
    
    def in_col(num, col):
        return num in (board[i][col] for i in range(9))
    
    def in_box(num, row, col):
        box_row = (row // 3) * 3
        box_col = (col // 3) * 3
        
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return True
        return False
    
    def find_empty_position():
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    return i, j
        return None
    
    def find_solution():
        empty_pos = find_empty_position()
        if not empty_pos:
            return True
        
        row, col = empty_pos
        for num in range(1, 10):
            if is_valid(num, row, col):
                board[row][col] = num
                if find_solution():
                    return True
                board[row][col] = 0
        return False
    
    find_solution()
    return board
            


# TEST 코드 입니다. 주석을 풀고 실행시켜보세요

print(solution(
[
 [5, 3, 0, 0, 7, 0, 0, 0, 0],
 [6, 0, 0, 1, 9, 5, 0, 0, 0],
 [0, 9, 8, 0, 0, 0, 0, 6, 0],
 [8, 0, 0, 0, 6, 0, 0, 0, 3],
 [4, 0, 0, 8, 0, 3, 0, 0, 1],
 [7, 0, 0, 0, 2, 0, 0, 0, 6],
 [0, 6, 0, 0, 0, 0, 2, 8, 0],
 [0, 0, 0, 4, 1, 9, 0, 0, 5],
 [0, 0, 0, 0, 8, 0, 0, 7, 9],
])
)


'''
반환값 : 
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9],
]
'''



print(solution(
[
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
])
)



'''
반환값 : 
[
[1, 2, 3, 4, 5, 6, 7, 8, 9],
[4, 5, 6, 7, 8, 9, 1, 2, 3],
[7, 8, 9, 1, 2, 3, 4, 5, 6],
[2, 3, 4, 5, 6, 7, 8, 9, 1],
[5, 6, 7, 8, 9, 1, 2, 3, 4],
[8, 9, 1, 2, 3, 4, 5, 6, 7],
[3, 4, 5, 6, 7, 8, 9, 1, 2],
[6, 7, 8, 9, 1, 2, 3, 4, 5],
[9, 1, 2, 3, 4, 5, 6, 7, 8],
]
'''

12-3. 합격자가 되는 모의 테스트

• 문제49_피로도
• 문제50_N-퀸