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

문제

• 스타트와 링크(백준14889)

풀이

문제 해석을 하자면,

• 두 팀의 점수 차이가 가장 작은(ex:0) 값을 구하라

풀이

• 크게 2가지를 구현하면 된다.
  • 팀나누기 -> 재귀 (N개 중 N/2개 택)
    • 재귀로 안하면 for문을 수도없이 사용하게 되어서 재귀로 돌렸다.
    • 그런데, 다른사람 풀이가 궁금해서 찾아보니 “조합론”을 사용하였다.
    • “조합” 으로 구현하면 딱히 visited도 필요없어서 더 간단하다.
    • 하고싶은대로 구현하자.
  • 계산하기 -> 2중 for (N/2개 중 2개 택)
• 단, 타입 조심 및 좌표 조심하자

코드

public static int[][] inArr = new int[22][22];
public static boolean[] visited = new boolean[22];
public static int[] outArr = new int[22];
public static int N;
public static int result = Integer.MAX_VALUE;

public static void cal() {
    // 먼저, 반대팀 숫자 구하기
    int[] outArr2 = new int[22]; // outArr에 없는 숫자들 -> 즉, 반대 팀의 숫자
    boolean[] visited2 = new boolean[22];
    for(int i=0; i<N/2; i++) { // 한팀의 크기 : N/2
        for(int j=1; j<=N; j++) { // 번호는 총 N
            if(outArr[i]==j) visited2[j]=true;
        }
    }
    int idx = 0;
    for(int i=1; i<=N; i++) {
        if(visited2[i]) continue;
        outArr2[idx++] = i;
    }

    // debug -> 숫자 출력 해보기
    //		for(int i=0; i<N/2; i++) {
    //			System.out.print(outArr[i]+" ");
    //		}
    //		System.out.println();
    //		for(int i=0; i<N/2; i++) {
    //			System.out.print(outArr2[i]+" ");
    //		}
    //System.out.println();

    // 2. 계산하기
    int cal1 = 0;
    int cal2 = 0;
    for(int i=0; i<(N/2)-1; i++) {
        for(int j=i+1; j<N/2; j++) {
            int idx1 = outArr[i]-1;
            int idx2 = outArr[j]-1;
            cal1 += inArr[idx1][idx2] + inArr[idx2][idx1];
        }
    }
    for(int i=0; i<(N/2)-1; i++) {
        for(int j=i+1; j<N/2; j++) {
            int idx1 = outArr2[i]-1;
            int idx2 = outArr2[j]-1;
            cal2 += inArr[idx1][idx2] + inArr[idx2][idx1];
        }
    }
    int diff = Math.abs(cal1-cal2);
    result = Math.min(result, diff);
}

// dfs. 숫자쌍 출력 -> 재귀로 구현하려면 idx, 백트래킹 필수
public static void dfs(int depth, int idx) {
    //base condition -> visited
    if(depth == N/2) {
        cal();
        return;
    }
    //recursion
    // 1. 팀나누기
    for(int i=idx; i<=N; i++) {
        if(visited[i]) continue;
        visited[i]=true;
        outArr[depth] = i;
        dfs(depth+1, i);
        visited[i]=false; // backtracking
    }
}

public static void main(String[] args) throws Exception {
    //init
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    for(int i=0; i<N; i++) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
            inArr[i][j] = Integer.parseInt(stk.nextToken());				
        }
    }
    //run
    visited[1]=true; // 1은 미리 넣고 시작
    outArr[0] = 1;
    dfs(1,1);
    //output
    System.out.println(result);
}

느낀점

생략