Backtracking

🧵 백트래킹(Backtracking)

해를 찾는 도중에 막히면(해가 아니면) 되돌아서 다시 해를 찾아가는 기법

최적화 문제, 결정 문제(문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'로 답하는 문제. ex: 미로 찾기, n-Queen 문제, Map cloring, 부분 집합의 합(Subset Sum)문제 등)를 해결

어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감

어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않음

반대로 해답의 가능성이 있으면 유망함.

 

가지치기(Pruning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않음.

1. 상태 공간 Tree의 깊이 우선 검색을 실시

2. 각 노드가 유망한지를 점검

3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속

 

백트래킹	깊이 우선 탐색
어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임	모든 경로를 추적
가지치기(Prunning)
불필요한 경로의 조기 차단
N! 가지의 경우의 수를 가진 문제에 대해 백트레킹에 가하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간(Exponential Time)을 요하므로 처리 불가능	N!가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 가하면 처리 불가능한 문제
모든 후보를 검사하지 않음	모든 후보를 검사

백트랙킹의 예로 미로에서 2차원 리스트 visited를 만들고 방문한 정점들을 기록하는 것이 있다.

깊이 우선 탐색은 백트래킹의 구체적인 형태다.

 

 

🍯 백트래킹 예시

# 백준 'N과 M (1)'에서
def dfs() :
    if len(s) == m :
        print(' '.join(map(str, s)))    # 공백으로 구분
        return

    for i in range(1, n+1) :    # 1부터 n까지의 수
        if i not in s :
            s.append(i)
            dfs()
            s.pop()

 

// 백준 1759. 암호 만들기 중에서
public static void find(int start, int depth) throws IOException{
        if(depth == L){
            if(check()){
                for(int i=0; i<C; i++){
                    if(visited[i]) bw.write(str[i]);    
                }
            }else return;
            bw.write("\n");
        }

        for(int i=start; i<C; i++){
            visited[i]=true;
            find(i+1, depth+1);
            visited[i]=false;
        }
    }

정렬을 하려면 start 파라미터가 있어야 한다.

i=start가 아닌 i=0이면 무한 반복이 일어날 것이다.

재귀호출 후 for문은 처음부터 시작되기 때문이다.

start를 지정해주면 원하는 위치에서부터 시작

 

// 백준 2023. 신기한 소수 중에서
private static void dfs(String s, int cnt){
        if(cnt == N){
            sb.append(s+'\n');
            return;
        }
        for(int i=1; i<=9; i++){
            if(isPrime(Integer.parseInt(s+i))){
                dfs(s+i, cnt+1);
            }
        }
    }

중복도 고려해야 해서 파라미터에 소수를 만드는 문자열이 있다.

 

 

# 백준 '가장 큰 금민수' 문제 중에서
N=int(input())
ans=0

def dfs(num) :
    global ans
    if int(num) > N :
        return
    elif ans < int(num) :
        ans=int(num)

    for i in ['4', '7'] :
        num+=i
        dfs(num)
        num=num[:-1]

dfs('4')
dfs('7')
print(ans)

순서를 따지지 않기 때문에 함수 호출이 두 번이다.

 

 

# 백준 '2661. 좋은수열'문제 중에서
# https://sungmin-joo.tistory.com/66
def back_tracking(idx) :
    for i in range(1, (idx//2)+1) :
        if s[-i:] == s[-2*i : -i] : return -1		# 가지치기

    if idx == n :
        for i in range(n) : print(s[i], end='')
        return 0

    for i in range(1, 4) :
        s.append(i)
        if back_tracking(idx+1) == 0 :
            return 0
        s.pop()

뒤에서부터 수열을 비교한다.

 

 

 

참고 👉 SW expert academy 파이썬 SW문제해결 기본 - Stack2 2차시 02 백트래킹

 

https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search

What's the difference between backtracking and depth first search?