[BOJ] 백준 [16198] 에너지 모으기JAVA

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

16198번: 에너지 모으기

📝문제

📝풀이

DFS 완전 탐색 문제이다.

1 2 3 4 가 주어질 때
(3) 번을 고를 경우 => energy += 2*4 가 되고 1 2 4 가 남는다.
1 4 는 고를 수 없기 때문에 남은 2번을 고르면 energy += 1*4 를 하면 최종적으로 12가 나온다.

List 하나 선언해서 DFS를 돌리고 해당 위치 x 를 remove 한 뒤 
백트래킹을해서 다시 x 를 넣어 주는 식으로 하는 것이 일반적인 풀이다.

다른풀이)
union-find 가 생각이나서 next[] 라는 배열 하나 더 선언 한 뒤에 자기 자신 위치를 초기로 가지고 있다가
left 나 right 값이 방문 되어 있을 경우 그 다음 left나 right 를 찾을 수 있는 메서드를 이용하였다.

백트래킹 할 때는 해당위치가 x라고 하면 next[x]=x 이런 식으로 인덱스를 복구도 같이 진행.

package baekjoon;

import static java.util.Arrays.*;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
import java.util.stream.Collectors;

public class Main {

    static int maxEnergy = Integer.MIN_VALUE;
    static int n;
    static int[] energy;
    static boolean[] visit;
    static int[] next;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        energy = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        visit = new boolean[n];
        next = new int[n];
        for (int i = 0; i < n; i++)
            next[i] = i; // 현재 위치는 자기 자신

        getEnergy(0, 0);
        System.out.println(maxEnergy);
    }

    public static void getEnergy(int depth, int totalEnergy) {

        if (depth == n - 2) { // 최대값 갱신
            maxEnergy = Math.max(totalEnergy, maxEnergy);
        }

        for (int i = 1; i < n - 1; i++) {

            if (!visit[i]) { // 만약 방문 안한 곳이면
                visit[i] = true;
                getEnergy(depth + 1, totalEnergy +
                        energy[findRight(i)] * energy[findLeft(i)]); // 좌우로 방문된 곳 제외하고 새로 찾은 값
                visit[i] = false;
                next[i] = i;
            }
        }
    }

    public static int findRight(int x) {

        if (!visit[x]) // 현재 위치가 방문안한 곳이면 해당 인덱스 return
            return x;
        return next[x] = findRight(x + 1); // 다음 위치 return
    }

    public static int findLeft(int x) {

        if (!visit[x])
            return x;
        return next[x] = findLeft(x - 1);
    }
}