[노트] 백트래킹

# 백트래킹

- 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서, 이 경우가 답이 될 수 없으면 그 노드의 이전(부모)로 돌아간다.

- 구현을 하면 재귀 형태가 된다.

- 재귀 함수는 탈출 조건이 필요한데, 탈출 조건은 해를 만족하였을 때로 하면 된다.

 

# 백트래킹의 포맷

def backtrack(candidate):
	# 만약 현재 후보군이 유효한 해라면 정답 처리하고 backtrack 함수를 종료
    if find_solution(candidate):
        output(candidate)
        return
    
    # 반복문을 돌면서 가능한 모든 후보군에 대해 탐색
    for next_candidate in list_of_candidates:
    	# 유효한 후보군인 경우에만 탐색 진행
        if is_valid(next_candidate):
            # 이 후보군을 우선 추가하고,
            place(next_candidate)
            # 후보군을 추가한 상태에서 다음 후보군에 대해서 탐색 진행
            backtrack(next_candidate)
            # 해당 후보군에 대한 탐색을 종료한 이후에는 제거
            remove(next_candidate)

 

 

 

# 순열 구하는 문제

n, m = map(int, input().split())

res = []
def f():
    if len(res) == m:
        print(*res)
        return

    for i in range(1, n+1):
        if i not in res:
            res.append(i)
            f()
            res.pop()

f()

 

 

 

# 스도쿠 문제

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

def check_row(x, a):
    for i in range(9):
        if a == mat[x][i]:
            return False
    return True


def check_col(x, a):
    for i in range(9):
        if a == mat[i][x]:
            return False
    return True


def check_box(x, y, a):
    x, y = x//3*3, y//3*3

    for i in range(3):
        for j in range(3):
            if a == mat[x+i][y+j]:
                return False
    return True


def f(num):
    if num == len(blank):
        for m in mat:
            print(*m)
        exit(0)

    for i in range(1, 10):
        x, y = blank[num]

        if check_row(x, i) and check_col(y, i) and check_box(x, y, i):
            mat[x][y] = i
            f(num+1)
            mat[x][y] = 0


mat = []
blank = []
for _ in range(9):
    line = list(map(int, input().split()))

    for i in range(9):
        if not line[i]:
            blank.append((_, i))

    mat.append(line)

f(0)

 

1. 처음 데이터를 입력받을 때 빈칸의 좌표를 따로 blank 배열에 저장한다. 
2. 백트래킹 재귀함수 실행
   1. 탈출 조건 : 빈칸을 전부 채웠을 때. 출력 후 바로 프로그램 종료
   2. 1~9 까지의 모든 수에 대하여, 반복문을 수행함
   3. 빈칸의 좌표를 꺼내고, 가로/세로/블럭 전부 체크 후 들어갈 수 있으면 빈칸을 채우고, 다음 블럭으로 감

 

 

# N-Queen 문제

n = int(input())

board = [[False]*n for _ in range(n)]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

res = 0


def f(row):
    global res
    if row == n:
        res += 1
        return

    for col in range(n):
        if is_safe(row, col):
            board[row][col] = True
            f(row+1)
            board[row][col] = False


def is_safe(r, c):
    for i in range(8):
        nr, nc = r, c
        while True:
            nr, nc = nr+dx[i], nc +dy[i]
            if not (0<=nr<n and 0<=nc<n): break
            if board[nr][nc]:
                return False

    return True

f(0)
print(res)