[백준] 2529 부등호 - 백트래킹 (Python)

아직 언제 재귀를 써야 하고, 언제 dfs 를 써야 하고, 언제 백트래킹을 써야 하는지 잘 모르겠다 ㅜㅜ 이 문제는 백트래킹으로 들어간 문제인데 그걸 아는데도 백트래킹이 무엇인지 제대로 몰라서 아주 헤맸다.

 

먼저 다시 정리해보고자 한다. 백트래킹이란 재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어가는 것이다.

즉, 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 다시 해를 찾는 것이다. 여기서 중요한 점은 더 이상 탐색할 필요가 없는 상태를 제외하는 것인데 이를 가지치기 라고 한다.

백트래킹은 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 DFS(깊이 우선 탐색), BFS (너비 우선 탐색) 으로 모두 구현이 가능하다. DFS 와 백트래킹의 차이는 다음과 같다. DFS 는 깊이 우선 탐색으로 모든 경로를 탐색한다. 모든 경로를 탐색하는 특징으로 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이진 못한다.

이미지 출처 : https://velog.io/@vagabondms/DFS-vs-BFS

 

 

부등호 문제에서 확인해야 할 미션은 4 가지다.

 

1. 숫자를 선택해야 한다 (0~9)

2. 부등호 조건이 맞는지 확인해야 한다.

3. 정답을 저장해야 한다.

4. 최대와 최소를 분리해야 한다.

 

먼저 부등호 조건을 확인하는 check 함수와 숫자를 선택하고, 탐색하고, 조건을 만족하는 정답을 저장하는 backtracking 함수를 나누었다. backtracking 은 재귀 알고리즘인데 base case 를 끝날 때까지 반복하므로 idx == k + 1 이라는 기저 조건을 설정해주었다. 문제에서 k + 1 개의 출력 결과를 원했기 때문이다. 0 부터 9 까지 for 문을 사용하고 check 함수를 통해 부등호 조건이 만족하는지 먼저 확인했다. 만약 만족하면, used 배열에 체크하고 다음 자리로 이동하여 재귀를 호출해 반복한다. 숫자 사용을 완료하면 다시 미사용 상태로 되돌려둔다. 한 경로에서 사용한 숫자를 다른 경로에서도 사용할 수 있게 하기 위해서이다. 한 경로에서 사용한 숫자를 다른 경로에서 다시 사용하려면, 각 탐색이 끝날 때마다 해당 숫자를 다시 미사용 상태로 되돌려야 한다.

def check(i, j, oper):
    if oper == "<":
        return i < j  # 부등호가 <일 때, i < j 인지 확인
    else:
        return i > j  # 부등호가 >일 때, i > j 인지 확인
    
def backtracking(idx, num):
    if idx == k + 1:  # 숫자 k+1개를 모두 선택한 경우
        answer.append(num)  # 정답 리스트에 숫자 저장
        return
    for i in range(10):  # 0부터 9까지 숫자 시도
        if not used[i]:  # 해당 숫자가 아직 사용되지 않았으면
            if idx == 0 or check(num[idx-1], str(i), oper[idx-1]):  # 부등호 조건을 만족하면
                used[i] = True  # 해당 숫자를 사용 중으로 표시
                backtracking(idx + 1, num + str(i))  # 다음 자리로 이동하여 재귀 호출
                used[i] = False  # 해당 숫자 사용 완료 후 다시 미사용 상태로 되돌림
    
k = int(input())  # 부등호의 개수 입력
oper = list(input().split())  # 부등호 리스트 입력

used = [False] * 10  # 숫자의 사용 여부를 기록하는 리스트
answer = []  # 정답을 저장할 리스트
backtracking(0, '')  # 백트래킹 시작

answer.sort()  # 정답 리스트 정렬
print(answer[-1])  # 가장 큰 숫자 출력
print(answer[0])  # 가장 작은 숫자 출력