백준[15661] - 링크와 스타트

• 문제: https://www.acmicpc.net/problem/15661
• 분류: 백트래킹, 비트마스킹
• 난이도: G5
• 소요시간: 30m
• 자아성찰:
  • DFS (조합)을 이용해서도 풀 수 있는 문제인 것 같았다.
    • 모든 경우에 대해 boolean 배열을 만들어 true/false 설정 및 계산 (재귀)
  • 나는 팀에 속하거나(1) / 속하지 않거나(0) 의 두가지 경우라는 생각에서 비트마스킹으로 풀어보았다.
    • 각 경우의 수를 이진수로 변환해 0과 1로 표현
    • Integer.toBinaryString(string) 이용
    • 나머지 자릿수는 String.repeat()을 통해 0으로 채워 N 자릿수 맞춤
    • String.toCharArray()를 통해 문자 배열로 만든 후 차이 계산
  • 최솟값이 0인경우 System.exit(0)을 통해 프로그램을 종료시키도록 했는데, 이런 케이스가 많은지 시간을 많이 줄일 수 있었다.

* 경우의 수 (이진수) = 1 ~ (2^N - 2) / 2
* ex) N = 4일 때 1 ~ 7
* 0001 (1)
* 0010 (2)
* 0011 (3)
* 0100 (4)
* 0101 (5)
* 0110 (6)
* 0111 (7)
* ----
* 1000 (8) -> 0001과 같은 결과

---

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

public class B_15661 {

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

    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];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                S[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        /*
         * 경우의 수 (이진수) = 1 ~ (2^N - 2) / 2
         * ex) N = 4일 때 1 ~ 7
         * 0001 (1)
         * 0010 (2)
         * 0011 (3)
         * 0100 (4)
         * 0101 (5)
         * 0110 (6)
         * 0111 (7)
         * ----
         * 1000 (8) -> 0001과 같은 결과
         */
        int loop = (int)(Math.pow(2, N) - 2) / 2;
        for (int n = 1; n <= loop; n++) {
            String s = Integer.toBinaryString(n); // n에 대해 이진수 변환
            StringBuilder sb = new StringBuilder();
            sb.append("0".repeat(N - s.length())); // N - s.length만큼 앞에 0 붙임
            sb.append(s); // s 뒤에 붙여 N자리 이진수로 변환
            char[] team = sb.toString().toCharArray();
            calc(team);
        }
        System.out.println(min);
    }

    private static void calc(char[] team) {
        int start = 0;
        int link = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (team[i] == team[j] && team[i] == '0') {
                    start += S[i][j] + S[j][i];
                }
                if (team[i] == team[j] && team[i] == '1') {
                    link += S[i][j] + S[j][i];
                }
            }
        }
        min = Math.min(min, Math.abs(start - link));
        if (min == 0) { // 최솟값이 0인 경우 정답이므로 바로 출력 및 종료
            System.out.println(0);
            System.exit(0);
        }
    }
}