[JAVA] 백준 - 스타트와 링크 14889

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

onejunu.tistory.com/63?category=882329

[JAVA] 비트 연산자를 이용하여 조합 & 부분집합 & 부분집합 여부파악

비트 연산자를 이용하여 풀어 보았다.

 

import java.util.Scanner;

class Main{
    static int n;
    static int[][] arr;
    static boolean[] team;
    static int answer = 987654321;

    static public void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][];
        team = new boolean[n];
        int temp;
        for(int i=0;i<n;i++){
            arr[i] = new int[n];
            for(int j=0;j<n;j++){
                arr[i][j] = sc.nextInt();
            }
        }

        for(int i=0;i<1<<n;i++){
            int cnt = 0;
            for(int j=0;j<n;j++){
                if((i & (1<<j) )>0){
                    cnt++;
                }
            }
            if(cnt == n/2){
                for(int j=0;j<n;j++)  team[j] = (i&(1<<j))>0?true:false;
                temp = cal();
                answer = answer > temp?temp:answer;
            }
        }

        System.out.println(answer);
    }


    static public int cal(){
        int trueTeam=0,falseTeam = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(team[i]==team[j] && team[i]){
                    trueTeam += arr[i][j];
                }
                else if(team[i]==team[j] && !team[i]){
                    falseTeam += arr[i][j];
                }
            }
        }
        return Math.abs(trueTeam - falseTeam);
    }
}

 

다음은 dfs 를 이용해 적절히 cutting 을 통해 푼것이다.

 

컷팅하는 조건문이 정말 중요한것 같다. 조금만 잘못되도 깊은 재귀의 늪에 빠져 시간초과가 나니... 

 

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

class Main{
    static int n;
    static int[][] arr;
    static List<Integer> team1 = new ArrayList<>();
    static List<Integer> team2 = new ArrayList<>();
    static int answer = 987654321;

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

        for(int i=0;i<n;i++){
            arr[i] = new int[n];
            for(int j=0;j<n;j++){
                arr[i][j] = sc.nextInt();
            }
        }

        dfs(0);
        System.out.println(answer);
    }
    static void dfs(int idx){
        if(team1.size() > n/2 || team2.size() > n/2) return;

        if(idx == n){
            if(team1.size() == n/2 && team2.size() == n/2){
                cal();
            }
            return;
        }

        team1.add(idx);
        dfs(idx+1);
        team1.remove(team1.size()-1);

        team2.add(idx);
        dfs(idx+1);
        team2.remove(team2.size()-1);
    }

    static void cal(){
        int one=0,two=0;
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n/2;j++){
                if(i!=j){
                    one += arr[team1.get(i)][team1.get(j)];
                    two += arr[team2.get(i)][team2.get(j)];
                }
            }
        }
        int temp = Math.abs(one-two);
        answer = answer > temp ? temp : answer;
    }

}

 

 

dfs 와 비트연산자 풀이의 속도를 비교해 보았다.

 

1)비트연산자

2) dfs