[DFS/BFS/완전탐색] ▲ 10819번 - 차이를 최대로(DFS/완전탐색)

[백준] 10819번 - 차이를 최대로

풀이 시간: 20분이내

N개의 정수로 이루어진 배열 A에 있는 수의 순서를 적절히 바꿔 얻을 수 있는 식의 최댓값을 구하는 문제로 모든 경우의 수를 확인해봐야하는 완전탐색 문제다. 나중에 다시 풀어볼만한 문제!

(풀이1) permutations 라이브러리 이용

1) 문제 해결 아이디어

permuations를 이용하면 일단 순열을 따로 구현할 필요가 없기 때문에 쉽게 풀 수 있다.

 

2) 소스코드

from itertools import permutations

n = int(input()) 
arr = list(map(int, input().split()))  # n개의 정수
max_res = 0  # 최댓값

for a in permutations(arr):
  res = 0 
  for j in range(len(a) - 1):
      res += abs(a[j] - a[j + 1])
  if(max_res < res): max_res = res

print(max_res)

 

풀이 시간: 30분이내

(풀이2) DFS를 이용한 백트래킹

1) 문제 해결 아이디어

DFS를 이용하여 순열을 직접 구하는 방식이다. 반례를 찾아 오류를 고치느라 시간이 좀 걸렸다.

 

첫번째 오류. 틀렸습니다

주어진 테스트 케이스로는 통과를 했는데 막상 제출을 하면 바로 틀렸습니다가 나왔다. 처음에 무슨 문제인지 전혀 알아채지 못해 게시판에 있는 반례들을 검사해보면서 잘못된 점을 알게되었다.

처음에는 현재선택한 값이 이미 선택한 적이 있으면 선택되지 않게 코드를 짰는데 이게 문제가 되었다.

이 문제는 입력으로 들어온 리스트에 중복된 값이 있을 수 있다는 점을 고려하여야 한다!!

예를 들어, 입력이 1 0 2 2 3 이런식으로 들어오게 된다면 2번째 인덱스의 2와 3번째 인덱스의 2를 구분하지 않아 문제가 생긴다.

그러므로 값으로 체크하는게 아니라 해당 인덱스의 숫자가 사용되는지 여부를 체크하는 리스트가 필요하다!!

 

<반례 목록>

6
-5 0 -4 -3 -3 -2 
: correct = 14, wrong = 13

5
2 0 0 -1 3 
: correct = 12, wrong = 11

6
2 -4 -4 0 1 4 
: correct = 29, wrong = 28

4
0 -1 -4 5 
: correct = 19, wrong = 17

6
-5 -3 2 1 -5 5 
: correct = 38, wrong = 37

4
1 -3 -4 4 
: correct = 20, wrong = 19

4
2 3 4 -1 
: correct = 11, wrong = 10

4
-1 -5 2 1 
: correct = 16, wrong = 15

4
-2 1 -1 0 
: correct = 7, wrong = 6

5
-1 -1 0 -3 -4 
: correct = 12, wrong = 11

2) 소스코드

n = int(input()) 
arr = list(map(int, input().split()))  # n개의 정수
max_res = 0  # 최댓값
temp = []    # 순열을 담을 곳
check = [False] * (n + 1)   # 선택 여부  

# DFS
def dfs(depth):
  global max_res
  # 깊이가 n이 되면 값 계산 후 종료
  if depth == n:
    res = 0
    for i in range(depth - 1):
      res += abs(temp[i] - temp[i + 1])
    if res > max_res:  max_res = res    
    return
  # 깊이가 n이 안됬으면
  else:
    for i in range(len(arr)):
      # i번째 인덱스 값이 아직 선택하지 않았다면
      if not check[i]:
        check[i] = True  # 선택 체크  
        temp.append(arr[i])  
        dfs(depth + 1)
        check[i] = False # 선택 해제
        temp.pop()
    
dfs(0)
print(max_res)