[BOJ] 백준 14889 - 스타트와 링크 (자바)

DFS 백트래킹 ,, 비트연산

백트래킹과 비트연산 2가지 모두 풀었다.

모든 경우의 수만 구하면 문제는 쉽게 풀린다.

풀이

1. 모든 경우의 수를 구한다.

2. 경우의 수를 value[] 배열에 0과 1로 저장한다.

3. 반으로 나눠야 하므로 1의 개수가 value[]의 크기 /2 일때 그 다음 과정을 수행할 수 있다.

4. 스타트팀과 링크팀을 나눠야 하는데 value의 조건에 따라 start[]팀과 link[]팀으로 나눈다.

5. start[], link[] 배열에 저장되는 것은 팀원이다.

(1,2 가 스타트팀 3,4 가 링크 팀일 경우 start[0] = 0, start[1] = 1, link[0] = 2, link[1]= 3 이 저장된다. [0부터 시작될 경우])

6. start[], link[] 배열을 (n/2) (n/2) 탐색하여 arr[][] 배열을 통해 값을 얻어 스타트팀의 최종 점수와 링크 팀의 최종 점수를 구한다.

7. 두 값의 차이가 최소를 정하고 출력한다.

소스 

(비트연산)

import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
 
        int[] start = new int[n];
        int[] link = new int[n];
        int min = Integer.MAX_VALUE;
 
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
 
        for (int i = 1; i < 1 << n; i++) {
            int[] value = new int[n];
            int count = 0;
 
            int bit = i;
            for (int j = 0; bit != 0; j++, bit >>= 1) {
                if ((1 & bit) == 0) {
                    continue;
                }
                value[j] = 1;
            }
 
            for (int k = 0; k < n; k++) {
                if (value[k] == 1) {
                    count++;
                }
            }
            //-----------경우의 수를 구하고 난 후----------------//
            
            //팀의 인원이 정확히 2로 나누어졌을 때 만 다음과정을 실행 할 수 있다.
            if (count == n / 2) {
                int start_sum = 0;
                int link_sum = 0;
                int start_cnt = 0;
                int link_cnt = 0;
                //value[] 값이 1이면 스타트팀, 0이면 link 팀이 된다.
                for (int k = 0; k < n; k++) {
                    if (value[k] == 1) {
                        //start_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                        start[start_cnt++] = k;
                    } else {
                        //link_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                        link[link_cnt++] = k;
                    }
                }
                
                //두팀이 가질 수 있는 점수를 다 구한다.
                //(1,1) (2,2) 등이 발생할 때 값은 0이므로 따로 조건을 만들지 않았다.
                for(int x=0; x<n/2; x++){
                    for(int y=0; y<n/2; y++){
                        start_sum += arr[start[x]][start[y]];
                        link_sum += arr[link[x]][link[y]];
                    }
                }
                //최소값 구함
                if(min > Math.abs(start_sum- link_sum)){
                    min = Math.abs(start_sum- link_sum);
                }
            
            }
 
        }
 
        System.out.println(min);
 
    }
 
}
 

(DFS 백트래킹)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    static int[][] arr;
    static int[] result;
    static int N;
    static int count;
    static int[] start;
    static int[] link;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
 
        arr = new int[N][N];
        result = new int[N];
        start = new int[N];
        link = new int[N];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                // arr[i] = integer.parseint(str[i + 1]);
            }
        }
        DFS(0, 0);
        System.out.println(min);
    }
 
    public static void DFS(int start, int depth) {
 
        for (int i = start; i < N; i++) {
            result[i] = 1;
            count++;
 
            DFS(i + 1, depth + 1);
            result[i] = 0;
            count--;
        }
        //-----------경우의 수를 구하고 난 후----------------//
 
        if (count == N / 2){
            //print();
            calc();
        }
 
    }
 
    public static void print() {
        for (int i = 0; i < N; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
 
    public static void calc() {
        int start_sum = 0;
        int liNk_sum = 0;
        int start_cNt = 0;
        int liNk_cNt = 0;
        //value[] 값이 1이면 스타트팀, 0이면 link 팀이 된다.
        for (int k = 0; k < N; k++) {
            if (result[k] == 1) {
                //start_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                start[start_cNt++] = k;
            } else {
                //link_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                link[liNk_cNt++] = k;
            }
        }
 
        //두팀이 가질 수 있는 점수를 다 구한다.
        //(1,1) (2,2) 등이 발생할 때 값은 0이므로 따로 조건을 만들지 않았다.
        for (int x = 0; x < N / 2; x++) {
            for (int y = 0; y < N / 2; y++) {
                start_sum += arr[start[x]][start[y]];
                liNk_sum += arr[link[x]][link[y]];
            }
        }
        //최소값 구함
        if (min > Math.abs(start_sum - liNk_sum)) {
            min = Math.abs(start_sum - liNk_sum);
        }
 
    }
}