(코테) 백준_15661_링크와 스타트 *백트레킹 , 비트마스킹 + 브루트포스 코드

 

 

 

 

 

 

 

풀이 * 백트레킹

package test;
import java.util.*;
import java.io.*;

public class Backjun_15661_test {

	static int N;
	static int[][] list;
	static boolean[] visted ;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
				//	기본 값들 세팅
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		N = Integer.parseInt(br.readLine());
		visted = new boolean[N];
		list = new int[N][N];
		StringTokenizer st ; 
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int x=0;x<N;x++) {
				list[i][x] = Integer.parseInt(st.nextToken());				
			}			
		}		
				// 실행문 
		dfs(0);	
		System.out.print(min);
	}
	
	public static void dfs(int deep) {
		List<Integer> teamA = new ArrayList<>();
		List<Integer> teamB = new ArrayList<>();
		
		if(deep==N) {
			//팀 세팅부터 
			for(int i=0;i<N;i++) {
				if(visted[i]) teamA.add(i);
				else teamB.add(i);
			}
			
			if(teamA.size()<2 || teamB.size()<2) return;
			
			int a = ableChk(teamA);
			int b = ableChk(teamB);
			//값 비교 + 값 갱신
			min = Math.min(min, Math.abs(a-b)); 			
			return;
		}
		
		//dfs 백트레킹 조건은 팀 세팅?? true로 
		visted[deep] = true;
		dfs(deep+1);
		
		visted[deep] = false;		
		dfs(deep+1);	
	}
	
	
	public static  int ableChk(List<Integer> team) {
		int sum = 0;
		//14678
		for(int i =0;i<team.size();i++) {
			for(int x =i+1;x<team.size();x++) {
				int a =team.get(i);
				int b =team.get(x);
				sum += list[a][b] + list[b][a];
			}
		}	
		return sum;
	}
}

 

 

 

 

 

풀이 2   비트마스킹 + 브루트포스 코드 

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[][] S;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                S[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int total = 1 << N; // 2^N
        for (int mask = 1; mask < total - 1; mask++) { // 0과 2^N -1은 전체 or 공집합이므로 제외
            List<Integer> teamA = new ArrayList<>();
            List<Integer> teamB = new ArrayList<>();

            for (int i = 0; i < N; i++) {
                if ((mask & (1 << i)) != 0) teamA.add(i);
                else teamB.add(i);
            }

            if (teamA.size() == 0 || teamB.size() == 0) continue;

            int scoreA = getScore(teamA);
            int scoreB = getScore(teamB);
            min = Math.min(min, Math.abs(scoreA - scoreB));
        }

        System.out.println(min);
    }

    static int getScore(List<Integer> team) {
        int sum = 0;
        for (int i = 0; i < team.size(); i++) {
            for (int j = i + 1; j < team.size(); j++) {
                int a = team.get(i);
                int b = team.get(j);
                sum += S[a][b] + S[b][a];
            }
        }
        return sum;
    }
}