Baekjoon[JAVA] - 10819번 차이를 최대로(DFS)

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

---

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1

6
20 1 15 8 4 10

예제 출력 1

62

---

풀이

처음 문제를 접근할 때 가장 큰 값이 나오도록 정렬하여 풀고자 하여 

나름 규칙을 발견하고, 정답을 작성했다고 생각했는데,

https://github.com/hou27/problem_solving/commit/324b51b2bdcc399751844e268b77d8b539fcf574

baekjoon java 차이를 최대로 - 틀림 · hou27/problem_solving@324b51b

아니었다.

 

문제를 자세히 보니 배열의 최대 크기가 8로 제한된 문제였고, 

DFS(깊이 우선 탐색)으로 풀어도 시간 초과가 발생할 일은 없겠다는 걸 그제야 깨달았다...

 

DFS란?

: Depth-First Search(깊이 우선 탐색)

 

깊이를 우선적으로 탐색하는 방법으로,

여러 길이 있을 때 하나의 길을 완벽하게 탐색한 후 다른 길을 탐색하는 방식이다.

 

루트 노드에서 시작하여 탐색하고 그 다음 노드로 넘어가며

각각의 노드를 시작으로 할 때 해당 경우를 완벽하게 탐색하고 넘어간다.

 

보통 모든 경우의 수를 모두 탐색하고자 할 때 사용하게 되는 방법이다.

 

해를 엄청 빠르게 찾을 수도 있고,

최악의 경우 모든 경우를 탐색한 후에야 해를 찾게 되어 오래 걸릴 수 있다.

void main

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] nArr = new int[sc.nextInt()];
    int max = 0;

    for (int i = 0; i < nArr.length; i++) {
      nArr[i] = sc.nextInt();
    }

    sc.close();

    // dfs로 모든 경우의 수 탐색
    List<Integer> list = new ArrayList<>();
    for (int i : nArr) {
      list.add(i);
    }

    max = dfs(list, 0);

    System.out.println(max);
}

우선 main method이다.

 

배열의 크기를 입력받고, 그 값만큼의 정수를 입력받은 후

DFS(깊이 우선 탐색) 방식으로 가장 큰 값의 결과를 도출해내는 정수의 순서를 구하도록 하였다.

 

int dfs

private static int dfs(List<Integer> list, int idx) {
  if (idx == list.size() - 1) { // 마지막 원소까지 탐색했을 때
    int max = 0;
    for (int j = 0; j < list.size() - 1; j++) { // 식의 최댓값 계산
      max += Math.abs(list.get(j) - list.get(j + 1)); // 절대값으로 계산
    }
    return max;
  }

  int max = 0; // 최댓값 다시 초기화
  for (int j = idx; j < list.size(); j++) { // 모든 경우의 수 탐색
    // idx번째 원소와 j번째 원소를 바꿈
    int tmp = list.get(idx);
    list.set(idx, list.get(j));
    list.set(j, tmp);
    max = Math.max(max, dfs(list, idx + 1)); // 최댓값 갱신
    // 다시 원래대로 돌려놓음
    tmp = list.get(idx);
    list.set(idx, list.get(j));
    list.set(j, tmp);
  }

  return max;
}

가장 먼저 리스트의 첫번째 요소를 기준으로 탐색을 시작하며,

재귀 형태로 하나씩 다음 요소를 기준으로 탐색하며 최대의 값이 계산되는 경우를 찾는다.

 

 

전체 코드이다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] nArr = new int[sc.nextInt()];
    int max = 0;

    for (int i = 0; i < nArr.length; i++) {
      nArr[i] = sc.nextInt();
    }

    sc.close();

    // dfs로 모든 경우의 수 탐색
    List<Integer> list = new ArrayList<>();
    for (int i : nArr) {
      list.add(i);
    }

    max = dfs(list, 0);

    System.out.println(max);
  }

  private static int dfs(List<Integer> list, int idx) {
    if (idx == list.size() - 1) { // 마지막 원소까지 탐색했을 때
      int max = 0;
      for (int j = 0; j < list.size() - 1; j++) { // 식의 최댓값 계산
        max += Math.abs(list.get(j) - list.get(j + 1)); // 절대값으로 계산
      }
      return max;
    }

    int max = 0; // 최댓값 다시 초기화
    for (int j = idx; j < list.size(); j++) { // 모든 경우의 수 탐색
      // idx번째 원소와 j번째 원소를 바꿈
      int tmp = list.get(idx);
      list.set(idx, list.get(j));
      list.set(j, tmp);
      max = Math.max(max, dfs(list, idx + 1)); // 최댓값 갱신
      // 다시 원래대로 돌려놓음
      tmp = list.get(idx);
      list.set(idx, list.get(j));
      list.set(j, tmp);
    }

    return max;
  }

}

 

성공^^