알고리즘 풀이 - 백준 14889(스타트와 링크, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

2. 풀이

 

이 문제는 우선 N명의 사람들을 반으로 나누어 팀을 배정한 뒤 그에 따라 능력치를 계산해야 한다.

우선 팀을 반으로 배정하는 작업을 수행하려면 그 경우의 수를 모두 따져봐야 하므로 완전 탐색을 통해 해결 해야 한다.

그 이후, 능력치를 계산하기 위해서 배정된 상태에서 값을 계산하기만 하면 된다. 즉, 팀을 배정 시의 완전 탐색을 어떻게 사용하느냐의 문제이다.

 

① 재귀로 팀 배정하기

재귀를 통해 스타트, 링크팀을 각각 배정하는 방법을 사용할 수 있다. 현재 함수 상태를 통해 몇 명의 플레이어를 선택했는지 확인하고 전체 선택이 완료되면  팀 능력치를 계산한다.

N명을 2팀으로 나누고 N은 반드시 짝수이므로 각 팀에 N/2명씩 배정이 완료될 때까지 재귀를 반복하고 모두 배정이 될 때마다 팀 능력치를 계산하여 최소가 되는 경우를 찾아야 한다.

즉, 탈출 조건은 각 팀 배정 인원이 N명인 경우이며, 함수의 상태로는 현재 각 팀에 배정된 인원이 몇 명인지를 전달하면 된다.

 

② 순열로 팀 배정하기

각 인원을 1, 2로 치환하여 N/2 개씩 만들어서 순열 형태로 만들면 된다. 하지만 이는 순열을 구하는 데에 따른 시간이 소요되는 것이 크므로 문제 해결에 따른 시간은 더 오래 걸린다.

1은 스타트팀, 2는 링크팀이라고 가정하고 모든 순열을 구한 뒤 각 순열에서의 계산된 값을 기반으로 최소치를 구한다. 즉, N=6이라면 111222로 최초에 만든 뒤, 222111이 될 때까지 모든 순열을 구하고 능력치를 계산하면 된다.

순열을 더 이상 구할 수 없는 상태(마지막 순열, 위의 예시에서는 222111) 이라면 더 이상 수행하지 않는다.

 

③ 비트마스크로 팀 배정하기

비트는 0과 1로 이루어진 2진수이다. 따라서, N명에 대해 N/2는 0으로, 나머지는 1이 되는 모든 비트마스크 상태를 구하고, 해당 상태가 진행될 때마다 팀 능력치를 계산한다.

최초 모든 것이 0인 상태에서 전체 집합인 모든 비트가 1인 상태까지 완전 탐색을 수행하여 1과 0의 비트 수가 같은 경우에 능력치를 계산하면 된다.

 

코드를 통해 각 경우에 대한 정답을 구하는 방법을 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 재귀로 해결하기

import java.io.*;

public class Main{
    static int n;
    static int player[];
    static int S[][];
    static int ans = Integer.MAX_VALUE;
    static int start[];
    static int link[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        player = new int[n];
        S = new int[n][n];

        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < n; j++){
                S[i][j] = Integer.parseInt(line[j]);
            }
            player[i] = i;
        }

        start = new int[n/2];
        link = new int[n/2];

        // 재귀 방식으로 Team을 구성
        makeTeam(0, 0);

        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    private static void makeTeam(int s, int l){
        // 배정이 완료된 경우 계산 수행
        if(s + l == n){
            calc();
        }

        // start / link팀에 현재 반 씩 배정되지 않았으면 재귀를 통해 지속 배정
        if(s < n/2){
            start[s] = player[s+l];
            makeTeam(s+1, l);
        }

        if(l < n/2){
            link[l] = player[s+l];
            makeTeam(s, l+1);
        }
    }

    private static void calc(){
        int start_score = 0;
        int link_score = 0;

        // 배정된 인원 기반 점수 계산
        for(int i=0; i < n/2; i++){
            for(int j=0; j < n/2; j++){
                start_score += S[start[i]][start[j]];
                link_score += S[link[i]][link[j]];
            }
        }
        ans = Math.min(ans, Math.abs(start_score - link_score));
    }
}

 

② 순열로 해결하기

import java.io.*;

public class Main{
    static int n;
    static int player[];
    static int S[][];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        player = new int[n];
        S = new int[n][n];

        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < n; j++){
                S[i][j] = Integer.parseInt(line[j]);
            }
            
            // 최초 반은 1 나머지 반은 2로 치환하여 팀을 배정함
            if(i < n/2){
                player[i] = 1;
            } else {
                player[i] = 2;
            }
        }

        int ans = Integer.MAX_VALUE;
        while(true){
            // 현재 순열 상태에서 능력치 계산
            ans = Math.min(ans, calc());
            
            // 다음 순열을 구할 수 있는지 체크
            boolean isNext = getNext();
            if(!isNext) break;
        }

        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    private static int calc(){

        int min = Integer.MAX_VALUE;
        
        // start팀과 link팀을 따로 배정(현재 순열 값 기반)
        int start[] = new int[n/2];
        int link[] = new int[n/2];
        
        // 현재 몇 명 배정된 상태인지 확인
        int s=0; int l=0;
        
        // 각 배열에 인원 배정
        for(int i=0; i < n; i++){
            if(player[i] == 1){
                start[s++] = i;
            } else {
                link[l++] = i;
            }
        }
        
        int start_score = 0;
        int link_score = 0;
        
        // 배정된 인원 기반 점수 계산
        for(int i=0; i < n/2; i++){
            for(int j=0; j < n/2; j++){
                start_score += S[start[i]][start[j]];
                link_score += S[link[i]][link[j]];
            }
        }
        min = Math.min(min, Math.abs(start_score - link_score));
        return min;
    }

    // 다음 순열을 구하는 메소드
    private static boolean getNext(){
        int i = n-1;
        while(i > 0 && player[i-1] >= player[i]) i--;

        if(i <= 0) return false;

        int j = i-1;
        while(j < n-1 && player[j+1] > player[i-1]) j++;
        swap(i-1, j);

        j = n-1;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
        return true;
    }

    private static void swap(int i, int j){
        int temp = player[i];
        player[i] = player[j];
        player[j] = temp;
    }
}

 

③ 비트마스크로 해결하기

import java.io.*;

public class Main{
    static int n;
    static int S[][];
    static int ans = Integer.MAX_VALUE;
    static int start[];
    static int link[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        S = new int[n][n];

        // 주어진 input 점수값 배열 상에 저장
        for(int i=0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j=0; j < n; j++){
                S[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        // start 팀, link 팀 배열 생성. n/2로 하지 않은 이유는 Array Index Out Bound를 피하기위해
        start = new int[n];
        link = new int[n];

        // 0001 ~ 1111과 같이 초기 비트부터 끝까지 모두 탐색(0000은 제외), n=4일 때를 가정 시
        for(int i=1; i < (1 << n); i++){
            // start, link 팀에 배정된 인원 수 계산
            int s = 0;
            int l = 0;
            
            // 0~n-1자리의 비트를 각각 체크함
            for(int j=0; j < n; j++){
                // 각 자리가 0이 아니라면 start팀, 0이면 link팀에 배정
                if((i & (1 << j)) != 0){
                    start[s++] = j;
                } else {
                    link[l++] = j;
                }
            }
            
            // start, link 팀의 인원이 동일하지 않은 경우 다시 체크
            if(s != l){
                continue;
            }
            
            // start, link 팀의 인원이 동일한 경우 능력치 계산 수행
            calc();
        }

        bw.write(String.valueOf(ans));
        bw.flush();
        br.close();
    }

    private static void calc(){
        int start_score = 0;
        int link_score = 0;

        // 배정된 인원 기반 점수 계산
        for(int i=0; i < n/2; i++){
            for(int j=0; j < n/2; j++){
                start_score += S[start[i]][start[j]];
                link_score += S[link[i]][link[j]];
            }
        }
        ans = Math.min(ans, Math.abs(start_score - link_score));
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.