백준 [단계별로 풀어보기]: (22단계) "백트래킹", python

백준 [단계별로 풀어보기]: (22단계) "백트래킹", python

 

1. 문제번호 및 정답비율

22단계 재귀 : 문제번호 및 정답 비율

2. 문제별 필요 지식 및 풀이 포인트

# 1. 15649 N과 M (1)

 

# 2. 15650 N과 M (2)

 

# 3. 15651 N과 M (3)

 

# 4. 15652 N과 M (4)

 

# 5. 9663 N-Queen

참고 : 바킹독님의 블로그 [강추] https://blog.encrypted.gg/945

참고: https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-9663-N-Queen-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

# 6. 2580 스도쿠

 

# 7. 14888 연산자 끼워넣기

 

# 8. 14889 스타트와 링크

 

 

3. 문제별 풀이 코드

# 1. 15649 N과 M (1)
#1차시도 : nCr,nPr
'''
from itertools import permutations
n,m = map(int, input().split())
nums = [i for i in range(1, n+1)]
nPr = permutations(nums, m) #TypeError: Expected int as r
for i in nPr:
    for j in i:
        print(j, end=' ')
    print()
'''
#2차시도 : 백트래킹, 임의집하에서 원소의 순서를 선택하는 문제 푸는 데 적합
#참고 : https://jie0025.tistory.com/455
#https://veggie-garden.tistory.com/24
'''
def backtracking():
    if len(array) == m:
        print(" ".join(map(str, array)))
        return
    for i in range(1, n+1):
        if i not in array:
            array.append(i)
            backtracking()
            array.pop()
n,m = map(int, input().split())
array = []
backtracking()
'''
#3차시도 : 백트래킹, DFS로 제한조건을 위배하는 노드는 제외(가지치기)하는 것
n,m = map(int, input().split()) #입력을 리스트로 받고, stack쌓는 것과 비슷
s = []
visited = [False]*(n+1)
def dfs(): #dfs, 재귀로 반복 : 리스트s 안에 m개 요소가 쌓이면 출력해준다.
    if len(s) == m: #ex) m=2일 경우, s=[1,2]가 되면 출력
        print(' '.join(map(str, s)))
        return
    for i in range(1, n+1): #이미 방문한 경우 제외
        if visited[i]:
            continue
        visited[i] = True #방문처리 후, s에 값i추가. dfs 재실행함
        s.append(i)
        dfs()
        s.pop()
        visited[i] = False
dfs()


# 2. 15650 N과 M (2)
n,m = list(map(int,input().split()))
s = []
def dfs(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start,n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)


# 3. 15651 N과 M (3)
n,m= map(int,input().split())
s = []

def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        s.append(i)
        dfs()
        s.pop()
dfs()


# 4. 15652 N과 M (4)
n,m = map(int, input().split())
s = []
 
def dfs(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start, n+1):
        s.append(i)
        dfs(i)
        s.pop()
    
dfs(1)


# 5. 9663 N-Queen
## method
def sol(k): # k : 놓은 말 개수 - 점유 행 번호로도 활용 가능
    # 퀸 : 상하좌우 - x, y 좌표 확인 / 대각선 - (y=x 선상 : used_up) r+c 같으면. (y=-x 선상 : used_down) r-c같으면 놓을 수 없음.
    global n, cnt
    if k == n :
        cnt += 1
        return

    # i : 점유 열 번호로 활용 가능
    for i in range(n):
        if not used_c[i] and not used_up[k+i] and not used_down[(n-1)+k-i]:
            used_c[i] = True
            used_up[k+i] = True
            used_down[(n-1)+k-i] = True
            sol(k+1)
            used_c[i] = False
            used_up[k+i] = False
            used_down[(n-1)+k-i] = False

n = int(input())
maps = [[0]*n for _ in range(n)]
# 열 점유 여부
used_c = [False]*n
# y = x 선상 점유 여부
used_up = [False]*(2*(n-1)+1)
# y = -x 선상 점유 여부
used_down = [False]*(2*(n-1)+1)

cnt = 0
sol(0)
print(cnt)


# 6. 2580 스도쿠


# 7. 14888 연산자 끼워넣기
# 7. 14888 연산자 끼워넣기
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9

def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)


# 8. 14889 스타트와 링크
N = int(input())
board = [list(map(int,input().split())) for _ in range(N)]
visited = [False for _ in range(N)]
INF = 2147000000
res = INF

def DFS(L,idx):
    global res
    if L == N//2:
        A = 0
        B = 0
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    A += board[i][j]
                elif not visited[i] and not visited[j]:
                    B +=board[i][j]
        res = min(res, abs(A-B))
        return
    for i in range(idx,N):
        if not visited[i]:
            visited[i] = True
            DFS(L+1,i+1)
            visited[i] = False
            
DFS(0,0)
print(res)