[백준] 10819 차이를 최대로 - 백트래킹 (Python)

입력받은 수열을 사용하여 가능한 모든 순열을 생성하고 각 순열에서 인접한 두 숫자의 차이의 절댓값을 더한 값 중 최댓값을 찾는 문제를 해결하고자 했다.

 

1. 모든 순열 생성 2. 인접한 두 숫자의 차이의 절댓값 더하기 3. 최댓값을 찾기

 

먼저 새로운 순열을 저장할 배열, 중복을 확인할 배열, 가능한 최댓값을 갱신하기 위한 변수를 설정한다. 가능한 모든 순열을 탐색해야 하기 때문에 백트래킹 (모든 가능한 경우의 수를 탐색하는 알고리즘) 을 사용했다. 방문한 숫자를 되돌리기 위한 visited 배열과 순열을 구성하는 arr 배열을 통해 매번 새로운 순열을 구성한다.

 

base case 인 cur 이 n 이 되었을 때 즉 순열이 완성되면 total 변수를 사용하여 인접한 값들의 차이의 절댓값을 구하고 이를 answer 변수에 갱신한다.

n = int(input())
list = list(map(int,input().split()))
arr = [0] * n # 정답을 저장
visited = [0] * n # 각 숫자가 순열에 포함되었는지 여부
answer = -99999 # 가능한 최댓값을 저장하는 변수 나중에 max 로 갱신되도록 가장 작은 수로 설정

def recur(cur) :
    global answer
    
    # arr 가 완성되었을 때
    if cur == n :
        total = 0
        # 문제에서 주어진 식 실행
        for i in range(1,n) :
            total += abs(arr[i] - arr[i-1])
            
        # 최댓값으로 정답 갱신
        answer = max(answer, total)
        return
    
    for i in range(n) :
        if visited[i] : # 이미 사용한 숫자는 넘어감
            continue
        
        arr[cur] = list[i] # 순열의 현재 위치에 숫자 삽입
        visited[i] = 1 # 숫자를 사용했음을 표시
        recur(cur + 1) # 다음 위치에 대해 백트래킹 호출
        visited[i] = 0 # 방문 여부를 원래대로 돌려놓음
                
recur(0)
print(answer)