[BOJ] 2661. 좋은 수열(Python) / Backtracking

 

www.acmicpc.net/problem/2661

2661번: 좋은수열

깔끔한 Backtracking 문제였다.

1시간 22분 소요

 

Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다.

개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것이다.

• 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 
• 고려할 수 있는 경우의 수를 상태공간트리로 표현
• DFS 방식으로 후보군 확인
  • 상태공간트리 탐색하며 제약조건을 만족하지 않으면 해당 부분에서 파생될 수 있는 모든 경우의 수를 더이상 보지 않는다.
  • 이후 해의 후보가 될 만한 곳을 바로 넘어가서 탐색을 이어간다.
• 이를 통해 체크해야 하는 조건의 수를 확연히 줄일 수 있기 때문에 계산량을 줄일 수 있는 기법이다. 
• Promising : 조건 검사 기법
• Prunning : 가지치기. 조건에 맞지 않으면 그 부분의 탐색은 포기하고 다른 루트로 돌아서서 탐색 시간 절약

정리

Backtracking은

트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건이 부합하는지 체크(Promising),

만약 해당 트리에서 조건에 맞지 않는 노드는 더이상 DFS 탐색 진행하지 않고 가지를 쳐냄(Prunning)

 

가지치기할 때 좀 헤매면서 시간이 좀 걸렸다ㅠㅠ

• 길이 1보다 큰 temp에 대해(depth > 1)에 대해 부분수열이 동일한 것이 있다면 가지치기
  • 현재 depth에서 앞쪽으로 임의의 길이만큼 비교
• 길이가 N까지 처음으로 다다랐을 때, 값 출력하고 전역변수 flag를 True로 바꿈
• flag가 이미 True라면 더이상 볼 필요 없으므로 가지치기

 

파이썬 코드는 다음과 같다.

---

def backtracking(depth, temp):
    global flag
    if flag:
        return
    if depth > 1:
        for length in range(depth//2):
         # 동일한 부분수열이 있다면 가지치기
            if temp[depth-2*length-2:depth-length-1] == temp[depth-length-1:depth+1]:
                return
    if depth == N:
        flag = True
        print(temp)
        return
    for num in "123":
        backtracking(depth+1, temp + num)

N = int(input())
flag = False
backtracking(0, "")

---

• 시간 : 112ms / 메모리 : 122244ms
• 고찰 : 어렵지 않은 문제인데 가지치기를 할 때 길이가 2이상인 것에 대해 모두 해줬어야 하는데 짝수 자릿 수인 것만 해줘서 시간이 좀 오래 걸렸다. 그 부분만 수정하니 바로 pass 받았다. Backtracking은 가지치기가 핵심! Keep Going 하자.