[BaekJoon] 15661번 링크와 스타트 (Java) 문제 풀이 [Gold 5]

문제

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

 

어떻게 풀 것인가?

처음에는 부분집합을 통한 방법을 생각했다.

부분집합을 이용해서 팀을 나누는 방식을 생각했다. 이는 부분집합이 선택되고, 선택되지 않고 하는 방식이기 때문이었다. 하지만 코드에 대한 아이디어가 잘 떠오르지 않아서, 백트레킹 방법으로 다가갔다.

아래는 풀이에 대한 아이디어 접근이다.

1. 모든 조합을 만들어보고 능력치 계산해서 최솟값을 갱신하는 백트래킹 or 브루트포스 방식 사용.
2. visited[] 배열을 활용해 팀을 나눈다.
3. 한 팀이 정해지면 나머지는 자동으로 다른 팀이 된다.
4. 조합(Combination)으로 팀을 나누고, 능력치를 계산해서 차이를 구한다.
5. 최솟값으로 계속 갱신한다.
6. N/2까지만 조합을 구하면 중복을 막을 수 있다.

 

풀면서 놓쳤던점

백트레킹은 항상 어려운 것 같다..

 

이 문제를 통해 얻어갈 것

백트레킹을 통한 브루트 포스 접근법

 

내 코드 

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

public class Main {
    static int N;
    static int[][] S;
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = new int[N][N];
        visited = new boolean[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());
            }
        }

        // 팀 인원 수는 1명 이상 N/2명 이하
        for (int i = 1; i <= N / 2; i++) {
            combination(0, 0, i);
        }

        System.out.println(answer);
    }

    // 팀 조합을 만드는 메소드 (백트래킹)
    static void combination(int depth, int start, int r) {
        if (depth == r) {
            List<Integer> startTeam = new ArrayList<>();
            List<Integer> linkTeam = new ArrayList<>();

            for (int i = 0; i < N; i++) {
                if (visited[i]) startTeam.add(i);
                else linkTeam.add(i);
            }

            int startSum = 0, linkSum = 0;

            for (int i = 0; i < r; i++) {
                for (int j = i + 1; j < r; j++) {
                    int a = startTeam.get(i);
                    int b = startTeam.get(j);
                    startSum += S[a][b] + S[b][a];
                }
            }

            for (int i = 0; i < N - r; i++) {
                for (int j = i + 1; j < N - r; j++) {
                    int a = linkTeam.get(i);
                    int b = linkTeam.get(j);
                    linkSum += S[a][b] + S[b][a];
                }
            }

            answer = Math.min(answer, Math.abs(startSum - linkSum));
            return;
        }

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

 

참고

X