백준 알고리즘 - 스타트와 링크

짝수의 플에이어 수를 받으면, 먼저 스타트팀과 링크팀으로 나눈다.
팀을 나눌 때 중복을 허용하지 않도록 짰다.

ex) 4명 인 경우
스타트팀.   링크팀
1, 2.              3, 4
2,1.               4, 3
은 순서만 다를 뿐 멤버는 같기 때문에 중복이다.
팀을 선정 후 조합을 사용해서 능력치의 합을 구했다.

예전에 푼거라서 그런지..
코드가 많이 지저분 하다.....
로직을 더 간단히 하고 중복되는 부분도 고쳐야 될 것같다..
시간이 날 때 새로 풀어봐야겠다...

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    private static int N;
    private static int[][] S;
    private static int[] allMember;
    private static ArrayList<Integer> tempAllMember = new ArrayList<>();
    private static boolean[] visited;
    private static int[] beforeDividedTeam;
    private static int[] startTeam;
    private static int[] linkTeam;
    private static boolean[] startVisited;
    private static boolean[] linkVisited;
    private static int[] startCombi = new int[2];
    private static int[] linkCombi = new int[2];
    private static ArrayList<Integer> startAbilities = new ArrayList<>();
    private static ArrayList<Integer> linkAbilities = new ArrayList<>();
    private static ArrayList<Integer> diffBothTeam = new ArrayList<>();
    private static Stack<Integer> stack = new Stack<>();
    private static int escapeCondition = 0;
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        N = scn.nextInt();
        S = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                S[i][j] = scn.nextInt();
            }
        }
        scn.close();
        allMember = new int[N];
        visited = new boolean[N];
        beforeDividedTeam = new int[N / 2];
        startTeam = new int[N / 2];
        linkTeam = new int[N / 2];
        startVisited = new boolean[N / 2];
        linkVisited = new boolean[N / 2];
        allMember();
        DFS();
        for (int i = 0; i < linkAbilities.size(); i++){
            int start = startAbilities.get(i);
            int link = linkAbilities.get(i);
            int diff = 0;
            if ( start > link ) {
                diff = start - link;
            } else {
                diff = link - start;
            }
            diffBothTeam.add(diff);
        }
        int min = 100;
        for (int i = 0; i < diffBothTeam.size(); i++) {
            if (diffBothTeam.get(i) < min) {
                min = diffBothTeam.get(i);
            }
        }
        System.out.println(min);
    }
    private static void DFS_ability(int[] arr, boolean[] visit, int[] combination, ArrayList<Integer> abilities) {
        makeAllNoVisited(visit);
        for (int i = 0; i < arr.length; i++) {
            makeForwardVisited(i, visit);
            DFS_ability(i, 0, combination.length-1, arr, visit, combination, abilities);
            visit[i] = false;
        }
    }
    private static void DFS_ability(int idx, int depth, int maxDepth, int[] team, boolean[] visit, int[] combination, ArrayList<Integer> abilities) {
        combination[depth] = team[idx];
        if (depth == maxDepth) {
            escapeCondition++;
            int ability1 = S[combination[0]-1][combination[1]-1];
            int ability2 = S[combination[1]-1][combination[0]-1];
            int sum = ability1 + ability2;
            stack.push(sum);
            if (escapeCondition == (team.length * (team.length-1)) / 2) {
                int finalSum = 0;
                while (!stack.isEmpty()){
                    int tempAbility = stack.pop();
                    finalSum += tempAbility;
                }
                abilities.add(finalSum);
                escapeCondition = 0;
                stack.empty();
            }
        } else {
            for (int i = idx; i < team.length; i++) {
                if (visit[i])
                    continue;
                visit[i] = true;
                DFS_ability(i, depth + 1, maxDepth, team, visit, combination, abilities);
                visit[i] = false;
            }
        }
    }
    private static void allMember() {
        for (int i = 0; i < N; i++) {
            allMember[i] = i + 1;
            tempAllMember.add(i + 1);
        }
    }
    private static void makeForwardVisited(int idx, boolean[] arr) {
        for (int i = idx; i > -1; i--) {
            arr[i] = true;
        }
    }
    private static void makeAllNoVisited(boolean[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = false;
        }
    }
    private static void recoverTempAllMember() {
        tempAllMember.clear();
        for (int i = 0; i < allMember.length; i++) {
            tempAllMember.add(allMember[i]);
        }
    }
    private static void DFS() {
        for (int i = 0; i < allMember.length; i++) {
            makeForwardVisited(i, visited);
            DFS(i, 0);
            visited[i] = false;
        }
    }
    private static void DFS(int index, int depth) {
        beforeDividedTeam[depth] = allMember[index];
        if (depth == N / 2 - 1) {
            for (int i = 0; i < beforeDividedTeam.length; i++) {
                startTeam[i] = beforeDividedTeam[i];
                tempAllMember.remove(new Integer(beforeDividedTeam[i]));
            }
            for (int i = 0; i < tempAllMember.size(); i++) {
                linkTeam[i] = tempAllMember.get(i);
            }
            DFS_ability(startTeam, startVisited, startCombi, startAbilities);
            DFS_ability(linkTeam, linkVisited, linkCombi, linkAbilities);
            recoverTempAllMember();
        } else {
            for (int i = index; i < allMember.length; i++) {
                if (visited[i])
                    continue;
                visited[i] = true;
                DFS(i, depth + 1);
                visited[i] = false;
            }
        }
    }
}

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째