🙃 Backtracking

intro

🙃 backtracking이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 구현력을 필요로 한다. 현재에서 나올 수 있는 모든 경우의 수를 모아 둔 decision space를 만들고, decision space의 각 부분마다 뻗어 나가며 그 다음으로 나오는 deicision space에서 계속해서 뻗어나가며 탐색. 만약 뻗어나간 결과 문제 상황에 맞지 않으면, 그 자리에서 중단하고 다시 뒤로 후퇴하면서 올라가 또 다른 경우의 수로 뻗어나가며 탐색. 

 

🙃 즉, 요약하자면 재귀적으로 가능한 모든 case를 incrementally하게 탐색해나가면서 해당 문제 조건에 만족하지 않는 경우는 이전으로 돌아가(backtrack) 계속 솔루션을 찾는 기법(결론: 백트래킹은 그냥 문제 많이...). DFS와 다른 점은, DFS는 모든 case를 검색하며 뻗어나가지만, backtracking은 뻗어나가는 도중 맞지 않는다면 검색 없이 바로 중단. 따라서 백트래킹이라면 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 알고리즘으로, 무작정 모든 case를 일일이 확인하는 brute-force와는 차이가 있다. backtracking은 과거와 미래 상태를 모두 고려하여 뻗어나가거나 가지치기하는 탐색 알고리즘으로 brute-force보다 성능이 더 좋으며, 이 때 재귀가 기본적으로 쓰인다. 따라서 구현이 상당히 어렵..

backtracking example

① N과 M 기초((1) ~ (8))

🙃 대표 문제 BOJ N과 M (1)을 요약하며 backtracking 재귀에 익숙해지자.

 

※ BOJ 15649 N과 M (1)

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

조건 ①) 중복되는 수열은 딱 1번만 출력

조건 ②) 수열은 사전 순으로 증가하는 순서로 출력

(이 때 1부터 N까지의 자연수에서 수열 만들기)

 

(1)

→ track()과 backtrack 장치를 각각 기억해주면 된다. track()이라는 아래로 내려가는 파란색 화살표를 반복적으로 사용하므로 recursion

→ 두 가지 종류의 backtracking ① 도중에 조건에 맞지 않아 바로 위로 올라가는 backtracking / ② 정답을 모두 구해 해당 case가 다 끝나 다시 올라가는 backtracking: 이 때 다시 올라가기 위해서 위 예시와 같이 ans.pop()과 같은 장치 track() 이후 만들어줘야 한다.

N,M=map(int,input().split())
ans=[]
def track():
    if len(ans) == M: #completed
        print(*ans)
    else:
        for x in range(1,N+1):
            if len(ans) != 0 and x in ans:
                continue #backtrack 1
            else:
                ans.append(x)
                track()
                ans.pop() #backtrack 2
track()

: 함수 끝나는 if문 → 그렇지 않다면 backtrack 1 바로 할 것인지 if문 → backtrack1 안한다면 track() 내려가기 + track() 내려가기 이후 올라가기 코드

 

(2)

→ 또는, 도중에 가지치기 되는 backtracking을 명시적으로 continue문 구현 필요 없이 track() 되는 부분만 돌려 / 답을 구하고 난 뒤 쭉 올라가는 backtrack 장치만 만들어도 OK

N,M=map(int,input().split())
ans=[]
def track():
    if len(ans) == M: #completed
        print(*ans)
    else:
        for x in range(1,N+1):
            if len(ans) == 0 or x not in ans:
                ans.append(x)
                track()
                ans.pop() #backtrack
track()

② N과 M 심화((9)~(12))

※ BOJ 15663 N과 M (9)

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

조건 ①) 중복되는 수열은 딱 1번만 출력

조건 ②) 수열은 사전 순으로 증가하는 순서로 출력

(이 때 중복을 포함한,랜덤한 N개의 자연수에서 수열 만들기)

 

🙃 재귀적으로 도는 backtracking에서 주어진 배열에서 자연수는 최대 1번만 쓰이고 수열 중복 방지를 위해 위의 기초 backtracking에서 장치를 몇 가지 더 만들어주어야 한다. (1) visited [] 사용하여 not visited한 곳만 재귀 진행. 이 때 재귀 전 visited = True 설정하고, 재귀 함수 아랫줄, 즉 재귀 이후에는 pop()과 함께 visited = False 꼭 설정 필요 (이전 상태로 되돌리기이므로) / (2) 수열 중복 방지를 위해 바로 앞의 원소, 즉 마지막 원소 last만 비교하면 된다. 그 이유는 재귀의 특성상, 바로 앞의 원소와 같지 않다면 그 아래 쭉 탐색을 안해주기 때문.  

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
num,visited=[],[False]*N
def track():
    if len(num)==M:
        print(*num)
    else:
        last=0
        for i in range(len(nums)):
            if not visited[i] and last!=nums[i]:
                visited[i]=True
                num.append(nums[i])
                last=nums[i]
                track()
                num.pop()
                visited[i]=False
track()

③ N과 M BOJ 정리

Q. N개의 자연수 중에 조건에 만족하는 M개의 수열을 출력하는 문제

---

BaaaarkingDog