self.winter.(09-2). 백트래킹 _ 백준[15649~15652]

🧐 백트래킹 ( Backtracking )

🤔 백트래킹이란?

DFS의 일종인 백트래킹은 일반적인 DFS와 달리 가지치기(pruning)를 진행
모든 경우의 수를 탐색하는 대신 조건을 거는데, 다음과 같다.
- 유망(promising)하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서 다른 경우를 탐색한다.

백트래킹은 DFS, BFS 두가지로 구현이 가능하지만 일반적으로 DFS로 구현하는것이 더 편하다.
(BFS는 큐의 크기가 커질 수 있기 때문에 보통 일반적으로 DFS를 사용한다)
다만 트리의 깊이가 무한대가 될 때, BFS를 사용한다.
또한 일반적으로 DFS는 스택이나 재귀로, BFS는 큐로 구현한다.

백트래킹은 답이 될 수 없는 후보는 더이상 깊게 들어가지 않고 되돌아가는 방법이다.

 

 

 

🤔 백트래킹 수도코드

procedure backtracking(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtracking(s)
        s ← next(P, s)

reject(P,c): 만약 다음의 노드가 후보가 아닌다면 return으로 종료.
accept(P,c): 만약 현재 노드까지가 답과 일치한다면 답을 출력.
first(P,c): 후보 C의 첫번째 확장을 시작한다.
답이 없을때까지 다음 함수를 계속 반복.

 

 

 

🧐 백준 15649

🤫 해결의 실마리 .  백트래킹

DFS의 방법 중 하나인 백트래킹을 이용한다.
이때, 알고리즘의 핵심은 스택을 이용한 구현에서 함수의 호출방식이 스택의 동작방식임을 이용한다.
함수의 호출 = push,  함수의 종료 = pop과 같은 방식이기 때문이다.



🤔 Algorithm 과정 
1. 해당하는 경우를 스택에 push하고 동작이 끝나면 다시 빼내는 pop을 진행
2. 이렇게 진행할 때, 이미 선택한 숫자는 배제 (1 1은 안되므로)해야 하므로 가지치기(pruning)

 

🤫  solution_15649 (Backtracking)

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

stack = []
def f():
    if len(stack) == m:
        print(" ".join(map(str, stack)))
        return


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

f()

🤫  solution_15649 (itertools의  permutations 사용)

from itertools import permutations
n, m = map(int, input().split())
num = [i for i in range(1, n+1)]

ans = permutations(num, m)

for i in ans:
    for j in i:
        print(j, end=' ')
    print()

 

 

 

🧐 백준 15650~15652

🤫  solution_15650

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

stack = []
first = 1
def f(first):
    if len(stack) == m:
        print(" ".join(map(str, stack)))
        return


    for i in range(first, n+1):
        if i in stack:
            pass

        stack.append(i)
        f(i+1)
        stack.pop()
f(first)

🤫  solution_15651

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

stack = []
def f():
    if len(stack) == m:
        print(" ".join(map(str, stack)))
        return


    for i in range(1, n+1):
        stack.append(i)
        f()
        stack.pop()
f()

🤫  solution_15652

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

stack = []

first = 1
def f(first):
    if len(stack) == m:
        print(" ".join(map(str, stack)))
        return

    for i in range(first, n+1):
        stack.append(i)
        f(i)
        stack.pop()
f(first)​