차이를 최대로 - 10819 (C++, DFS)

[1]. 차이를 최대로 (C++)

[1.1] 문제

N개의 정수로 이루어진 배열 A가 주어진다, 적절히 정수의 순서를 바꿔 최댓값을 찾는 문제

 

[1.2] 해설

DFS 알고리즘을 적용해서 풀어보았다. 

배열의 크기가 3이고, 배열의 값이 [1, 2, 3 ] 일 경우를 생각하면 아래와 같이 총 3가지의 경우를 생각하면 구현하기 편하다. 방문한 경우, 방문하지 않은 경우, 탐색이 트리의 끝에 방문한 경우의 DFS Tree 를 생각하며 코드를 구현하면 편하다.

DFS Tree

(1). 방문한 경우

빨간색은 이미 배열에 있는 경우이기 때문에 방문할 필요가 없다, 따라서 해당 빨간색 트리는 탐색하지 않는다. 

(2). 방문하지 않는 경우

파란색은 방문하지 않았기에 방문하여 경우에 수를 계속해서 계산한다.

(3). 탐색이 트리의 끝에 방문한 경우

위에 그림의 경우, N이 3이 므로 Level 3에 달했을 때, 거쳐온 트리의 경우의 수의 차이를 더해서 최댓값일 경우 갱신하여 계산하면 된다.

[1.3]. 구현

#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
#define MAX 8
using namespace std;

int n, ans = INT_MIN;
int map[MAX];
bool visit[MAX];

// dfs
void dfs(int level, vector<int> v) {
  if (level == n) {
    int v_sum = 0;
    for (int i = 0; i < n - 1; i++) {
      v_sum += abs(v[i] - v[i + 1]);
    }
    ans = ans > v_sum ? ans : v_sum;
    return;
  }

  for (int i = 0; i < n; i++) {
    // 방문했는지 검사
    if (visit[i])
      continue;


    visit[i] = true;
    v.push_back(map[i]);

    dfs(level + 1, v);

    visit[i] = false;
    v.pop_back();
  }
}

int main() {
  // fast i/o
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);

  // input
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> map[i];
  }
  
  
  vector<int> v;
  dfs(0, v);

  cout << ans;
}

 

감사합니다.

 

 

- 문제 출처

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

10819번: 차이를 최대로