링크

스타트와 링크

문제

풀이

이 문제는 어떻게 풀어야 하는지는 쉬웠다.
그런데 시간초과가 나서 끙끙 앓다가 다른사람 풀이법을 참고했다.
나는 6개가 차면 dfs를 돌렸었는데 다른분들의 풀이는 원본의 절반을 탐색하면 dfs를 돌리는 방법을 사용했다. 그리고 방문한 곳만 계산하는 방법을 써서 되게 빠르게 탐색했다.

내풀이

        public static void cal(){
        int ans1 = 0;
        int ans2 = 0;

        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();

        for(int i=0;i<list.size()*2;i++){
            if(list.contains(i)){
                arr1.add(i);
            } else{
                arr2.add(i);
            }
        }

        for(int i=0;i<arr1.size()-1;i++){
            int current1 = arr1.get(i);
            int current2 = arr2.get(i);
            for(int j=i+1;j<arr1.size();j++){
                ans1 += matrix[current1][arr1.get(j)];
                ans1 += matrix[arr1.get(j)][current1];

                ans2 += matrix[current2][arr2.get(j)];
                ans2 += matrix[arr2.get(j)][current2];
            }
        }



            result = Math.min(result, Math.abs(ans1 - ans2));
            if(result == 0){
                System.out.println(result);
                System.exit(0);
            }


    }

나는 이런식으로 풀었지만

다른사람 풀이

public static void cal(){
        int ans1 = 0;
        int ans2 = 0;

        for(int i=0;i<visited.length-1;i++){
            for(int j=i+1;j<visited.length;j++){
                //스타트팀
                if(visited[i] && visited[j]){
                    ans1 += matrix[i][j];
                    ans1 += matrix[j][i];
                }
                //링크팀
                else if(!visited[i] && !visited[j]){
                    ans2 += matrix[i][j];
                    ans2 += matrix[j][i];
                }
            }

        }

        result = Math.min(result, Math.abs(ans1 - ans2));

    }

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

//14888
public class Main {
    public static int[][] matrix = null;
    public static List<Integer> list = new ArrayList<>();
    public static boolean[] visited = null;
    public static int result = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        visited = new boolean[n];
        matrix = new int[n][n];

        for(int i=0;i<n;i++){
            String[] elementArr = br.readLine().split(" ");

            for(int j=0;j< elementArr.length;j++){
                matrix[i][j] = Integer.parseInt(elementArr[j]);
            }
        }


        dfs(n, 0);
        System.out.println(result);

    }

    public static void dfs(int n, int start){
        if(list.size() == n/2){
//            System.out.println(Arrays.toString(visited));
            //System.out.println(list);

            cal();

            return;
        }


        for(int i=0;i<n;i++){
            if(!visited[i] && i>=start ){
                visited[i] = true;
                list.add(i);
                dfs(n, i);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }


    }

    public static void cal(){
        int ans1 = 0;
        int ans2 = 0;

        for(int i=0;i<visited.length-1;i++){
            for(int j=i+1;j<visited.length;j++){
                //스타트팀
                if(visited[i] && visited[j]){
                    ans1 += matrix[i][j];
                    ans1 += matrix[j][i];
                }
                //링크팀
                else if(!visited[i] && !visited[j]){
                    ans2 += matrix[i][j];
                    ans2 += matrix[j][i];
                }
            }

        }

        result = Math.min(result, Math.abs(ans1 - ans2));



    }


}

다른사람의 풀이를 보면 가독성도 좋고 훨씬 빠르다.