[백준] 15661 (Java) [완전탐색]

문제

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

 

 

알고리즘

완전탐색 (브루트포스)

 

 

풀이

먼저 메인함수에서 for문을 통해 최소1명부터~N명까지 pick을 하고

재귀를 통해 그에 맞게 팀을 start와 link로 구분하면 되는 문제였다.

 

 

코드

package com.company;

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

public class Test_BruteForce {
    static int N;
    static ArrayList<Integer> startList; //스타트
    static ArrayList<Integer> linkList; //링크
    static int ans = 123567890;
    static int[][] map;
    static int[] people; 
    
    //재귀를 통해 팀 나누기(start, link)
    static void dfs(int idx, int cnt, int pick) {
        if (cnt == pick) {
            startList = new ArrayList<>();
            linkList = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if (people[i]==1) { //반으로 나누기 위한 작업)
                    startList.add(i);
                }else{
                    linkList.add(i);
                }
            }

            getDiff();
            return;
        }

        for (int i = idx; i < N; i++) {
            people[i] =1;
            dfs(i+1, cnt + 1, pick);
            people[i]=0;
        }
    }

    //각 팀간의 점수 차이 구하기
    static void getDiff() {
        int startSum = 0;
        int linkSum = 0;
        for (int i = 0; i < startList.size(); i++) {
            for (int j = 0; j < startList.size(); j++) {
                startSum += map[startList.get(i)][startList.get(j)];
            }
        }

        for (int i = 0; i < linkList.size(); i++) {
            for (int j = 0; j < linkList.size(); j++) {
                linkSum += map[linkList.get(i)][linkList.get(j)];
            }
        }

        //System.out.println("statSum: "+startSum+", linkSum: "+linkSum);
        ans = Math.min(ans, Math.abs(startSum - linkSum));
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        people = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        //pick: 몇명을 선택할 것인지(최소 1명은 팀에 들어가야함)
        for (int pick = 1; pick <= N; pick++) {
            dfs(0, 0, pick);
        }

        System.out.print(ans);
    }
}