JAVA [Algorithm] - 백준 14889 스타트와 링크

 

📝문제 설명

 

---

📢입출력 예시

 

---

✏️문제 풀이

우선 N 값마다 만들 수 있는 팀의 경우의 수를 생각해보자

N = 4 인 경우                       N = 6인 경우

(0, 1) VS (2, 3)                         (0, 1, 2) VS (3, 4, 5)

(0, 2) VS (3, 4)                         (0, 1, 3) VS (2, 4, 5)

(0, 3) VS (1, 2)                         (0, 1, 4) VS (2, 3, 5)

                                                 (0, 1, 5) VS (2, 3, 4)

                                                 (0, 2, 3) VS (1, 4, 5)

                                                 (0, 2, 4) VS (1, 3, 5)

                                                 (0, 2, 5) VS (1, 3, 4)

                                                 (0, 3, 4) VS (1, 2, 5)

                                                 (0, 3, 5) VS (1, 2, 4)

                                                 (0, 4, 5) VS (1, 2, 3)

 

경우의 수를 나열하면 0을 포함한 나머지 경우의 수만 구하면 된다.

그리고 팀 효과를 계산하기 위해서는

 

N = 4일 때는 (0,1)의 값만 계산하면 되지만

N = 6일 때는 (0, 1, 2)의 팀이 만들어지므로 (0,1) + (0,2) + (1,2) + (1,0) + (2,0) + (2,1) 이렇게 6번 더해주면 된다.

단 (1,0), (2,0), (2,1)는 (0,1) (0,2) (1,2)를 거꾸로 배열한거기 때문에 더할 때는 완전탐색으로 더해준다.

즉 S[i][j] + S[j][i] 를 해줘야 한다는 의미이다.

 

그렇다면 해야될 것은

1. 팀 구성하기

2. 구성한 팀의 효과 계산

3. 효과 계산 후 최소값 최신화 하기

 

1번은 백트래킹의 기초인 N과 M의 문제와 유사하고

2,3번은 팀이 구성되면 계산만 해주는 로직만 구현하면 된다.

 

이때 한가지 고민했던 것이 팀을 구성은 어떻게 해야될 것인가? 어떤 자료형을 사용해야되나?

N = 6일 때는 어떻게 팀 효과를 계산해줘야 하나?

 

(0, 1, 2)를 선택해야 한다면 위에서 생각한 것 처럼 (0,1) + (0,2) + (1,2)를 더해주면 된다고 했다.

그러면 한번에 3개를 구하는 것보다는 2개씩 구해 따로 더해주면 될 것이다.

 

그리고 팀을 선택했다는 것을 나타내기 위해서는 visited 방문 배열을 사용하여 팀 선택되었다면 T, 안되었다면 F를 사용하였다.

package Baekjoon.BackTracking;

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

public class Baek14889 {

    static int N;
    static boolean[] visited;
    static int[][] synergy;
    static int minScore = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        N = Integer.parseInt(bufferedReader.readLine());
        visited = new boolean[N];
        synergy = new int[N][N];

        for(int i=0; i<N; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j=0; j<N; j++){
                synergy[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        backTracking(0,0);
        System.out.println(minScore);
    }

    private static void backTracking(int start, int depth){
        if(depth == N/2){
            cal();
            return;
        }

        for(int i=start; i<N; i++){
            if(!visited[i]) {
                visited[i] = true;
                backTracking(i+1,depth + 1);
                visited[i] = false;
            }
        }
    }

    private static void cal(){
        int start = 0;
        int link = 0;

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visited[i] && visited[j]){
                    start += synergy[i][j];
                }else if(!visited[i] && !visited[j]){
                    link += synergy[i][j];
                }
            }
        }

        int min = Math.abs(start - link);
        minScore = Math.min(min, minScore);
    }
}

 

 

---

💡새로 알게된 점

 

 

---