[java,백준14889]스타트와 링크 - 조합을 활용한 팀 분배 문제

DFS를 활용하여 N명을 두 팀으로 나누고, 각 팀의 능력치 차이의 최솟값을 구하는 문제입니다.

스타트와 링크(백준14889)


복잡한 예시를 시각화 해보자

예시 시각화:
N=6일 때 팀 분배 과정

능력치 배열 S:
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

팀 분배 예시:
스타트팀(1, 3, 6) vs 링크팀(2, 4, 5)
스타트팀 능력치: 
* S13 + S31 = 3
* S36 + S63 = 8
* S16 + S61 = 6
링크팀 능력치: 
* S24 + S42 = 5
* S45 + S54 = 8
* S25 + S52 = 6
차이(정답): |17 - 19| = 2



풀이

구현 시 주의사항

💡 두 번의 조합을 구현해야 합니다: DFS로 두 단계의 조합을 구현하여 모든 경우의 수를 탐색하는 방식으로 구현

  1. N명 중 N/2명을 선택하여 팀 나누기
  2. 각 팀에서 2명씩 선택하여 능력치 계산


핵심 구현 사항

  • 두 번의 조합
    • N개 중 N/2개를 선택하는 조합 -> 팀 나누기
    • 선택된 N/2개 중 2개를 선택하는 조합 -> 각 팀의 능력치 계산
  • 능력치 차이의 최솟값 갱신


팀 나누기 DFS

  • linkTeam() 의 경우 start 팀이 아닌 팀으로 조건문 사용하여 할당하면 됨
static void dfs(int depth, int idx) {
    if (depth == N/2) {
        linkTeam();
        sum = new int[2];
        startDfs(0,0);
        linkDfs(0,0);
        result = Math.min(result, Math.abs(sum[0] - sum[1]));
        return;
    }
    for (int i = idx; i < N; i++) {
        start[depth] = i;
        dfs(depth + 1, i + 1);
    }
}


능력치 계산 DFS

static void startDfs(int depth, int idx) {
    if (depth == 2) {
        int i = selectS[0], j = selectS[1];
        sum[0] += S[i][j] + S[j][i];
        return;
    }
    for (int i = idx; i < N/2; i++) {
        selectS[depth] = start[i];
        startDfs(depth + 1, i + 1);
    }
}



전체 코드

package newnew;

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

/**
 * 팀나누기가 핵심
 *  * 타입조심, 좌표조심
 *  * 1. 팀나누기 -> 재귀 (N개 중 N/2개 택)
 *  *  * 재귀의 경우 조합: N_C_N/2
 *  * 2. 계산하기 -> 2중 for 또는 재귀 (N/2개 중 2개 택)
 *  *  * 재귀의 경우 조합: N/2_C_2
 */
public class 스타트와링크_14889 {
  static int N;
  static int[][] S;
  static int[] start;
  static int[] link;
  static int result = Integer.MAX_VALUE;
  static int[] selectS = new int[2];
  static int[] sum = new int[2];

  /*
  만약 startDfs를 for문으로 한다면? 이런식
  int cal1 = 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];
    }
  }
   */

  static void startDfs(int depth, int idx) {
    if (depth == 2) {
      int i=selectS[0]; int j=selectS[1];
      sum[0]+=S[i][j]+S[j][i];
      return;
    }
    for (int i = idx; i < N / 2; i++) {
      selectS[depth]=start[i];
      startDfs(depth+1, i+1);
    }
  }
  static void linkDfs(int depth, int idx) {
    if (depth == 2) {
      int i=selectS[0]; int j=selectS[1];
      sum[1]+=S[i][j]+S[j][i];
      return;
    }
    for (int i = idx; i < N / 2; i++) {
      selectS[depth]=link[i];
      linkDfs(depth+1, i+1);
    }
  }

  //조합1: 전체 N개 중 N/2개 선택
  static void dfs(int depth, int idx) {
    if (depth == N/2) {
      //link 팀 결정 -> start 아닌 멤버들로
      linkTeam();
      //각 팀별 S값 계산
      sum=new int[2];
      startDfs(0,0); //조합2: 전체 N/2개 중 2개 선택
      linkDfs(0, 0);
      result = Math.min(result, Math.abs(sum[0] - sum[1]));
      return;
    }
    for (int i = idx; i < N; i++) {
      start[depth] = i;
      dfs(depth + 1, i + 1);
    }
  }

  private static void linkTeam() {
    int idx=0;
    for (int i = 0; i < N; i++) {
      boolean check = false;
      for (int j = 0; j < N / 2; j++) {
        if (start[j] == i) {
          check = true;
        }
      }
      if(check) continue;
      link[idx++]=i;
    }
  }

  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 + 1][N + 1];
    start = new int[N/2];
    link = new int[N/2];
    for (int i = 0; i < N; i++) {
      StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
      for (int j = 0; j < N; j++) {
        S[i][j] = Integer.parseInt(stk.nextToken());
      }
    }
    dfs(0, 0);
    System.out.println(result);
  }
}

주관적인 생각의 풀이이므로 틀린 부분 지적은 언제나 환영합니다⚡

댓글남기기

참고