[백준] 14889번 스타트와 링크 자바(백트래킹 , 비트마스킹)

 

분석

---

해당 문제는 백트래킹 , 비트마스킹 두 가지 방법으로 풀 수 있습니다.

 

1. 비트마스킹

 

비트 마스킹이란?

불리언 배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색 , 수정 등의 작업을 하는 것을 말합니다

- 큰돌의 터전 유튜브

 

더 자세한 사항은 이전에 블로그에 정리해 놓은 내용을 참고해주세요 

https://cb036133.tistory.com/91

[백준] 11723 집합 JAVA

 

static void dfs() {
    for (int i = 0; i < (1 << num) ; i++) {
        int cnt = 0;
        team = new boolean[num];
        for (int j = 0; j < num; j++) {
            if ((i & (1 << j)) != 0) {
                team[j] = true;
                cnt++;
            }
        }
        if (cnt == num / 2) cal();


    }
}

저는 비트마스킹을 이용해서 팀의 수가 반반이 되면 각 팀의 능력치 합을 빼주는 식으로 코드를 구성하였습니다.

 

2. 백트래킹

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

 

dfs를 이용하여 백트레킹을 구현할 수 있습니다.

static void dfs(int idx,int depth) {
        if (depth == num / 2) {
            cal();
            return;
        } else {
            for (int i = idx; i < num; i++) {
                if (check[i] == false) {
                    check[i] = true;
                    dfs(i+1,depth + 1);
                    check[i] = false;
                }
            }
        }
    }

 

코드 - 비트마스킹

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static int num;
    static int[][] arr;
    static boolean[] team;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        num = Integer.parseInt(br.readLine());
        arr = new int[num][num];
        team = new boolean[num];

        for (int i = 0; i < num; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < num; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs();

        System.out.println(min);
    }

    static void dfs() {
        for (int i = 0; i < (1 << num) ; i++) {
            int cnt = 0;
            team = new boolean[num];
            for (int j = 0; j < num; j++) {
                if ((i & (1 << j)) != 0) {
                    team[j] = true;
                    cnt++;
                }
            }
            if (cnt == num / 2) cal();


        }
    }

    static void cal() {
        int num1 = 0;
        int num2 = 0;

        for(int i=0;i<num-1;i++){
            for(int j=i+1;j<num;j++){
                if(team[i] == true & team[j] == true){
                    num1 += arr[i][j];
                    num1 += arr[j][i];
                }
                if(team[i] == false & team[j] == false){
                    num2 += arr[i][j];
                    num2 += arr[j][i];
                }
            }

        }


        int result = Math.abs(num1-num2);

        if(result == 0){
            System.out.println(0);
            System.exit(0);
        }

        if(min > result) min = result;
    }

}

 

코드 - 백트래킹

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Math.abs;

public class Main {
    static int[][] arr;
    static boolean[] check;
    static int num;
    static int result=Integer.MAX_VALUE;

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

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

    static void dfs(int idx,int depth) {
        if (depth == num / 2) {
            cal();
            return;
        } else {
            for (int i = idx; i < num; i++) {
                if (check[i] == false) {
                    check[i] = true;
                    dfs(i+1,depth + 1);
                    check[i] = false;
                }
            }
        }
    }

    static void cal() {
        int num1 = 0;
        int num2 = 0;

        for (int i = 0; i < num-1; i++) {
            for(int j= i+1;j<num;j++) {
                if (check[i] == true & check[j] == true) {
                    num1 += arr[i][j];
                    num1 += arr[j][i];
                }
                else if (check[i] == false & check[j] == false) {
                    num2 += arr[i][j];
                    num2 += arr[j][i];
                }
            }
        }
        int val = abs(num1 - num2);
        if(val == 0){
            System.out.println(0);
            System.exit(0);
        }

        result = Math.min(result,val);
    }
}