백준 14889번 스타트와 링크 :: 마이구미

이 글은 백준 알고리즘 문제 14889번 "스타트와 링크" 를 풀이한다.

삼성 SW 역량 테스트의 기출 문제이다.

본인은 DFS를 활용해 문제를 해결했다.

문제 링크 - https://www.acmicpc.net/problem/14499

DFS 참고

관련 문제 - http://mygumi.tistory.com/191

DFS 이해 - http://mygumi.tistory.com/102

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

문제는 N명의 인원을 N/2명의 두 팀으로 나누어 두 팀의 능력 차이의 최소값을 구하는 문제가 된다.

N명을 두 팀으로 나누는 모든 경우를 탐색해야하는 완전 탐색 문제가 된다.

본인은 3가지로 분류하였다. 즉, 3개의 함수로 나타낼 수 있다.

1. DFS를 통해 두 팀을 나누는 경우를 구한다.
2. 구해진 경우에서의 두 팀을 배열로 나타낸다.
3. 두 팀의 능력 차이를 구한다.

헷갈릴 수 있는 문제지만, 하나하나 쪼개서 생각하면, 문제를 쉽게 해결할 수 있다.

DFS 백트래킹을 이해하지 못했다면, 다음 링크를 참고바란다. (http://mygumi.tistory.com/191)

그래프 알고리즘 문제 풀이 - 그래프 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/graph

static int[][] map = new int[21][21];
static boolean[] visited = new boolean[21];
static int n, ans = Integer.MAX_VALUE;
 
private void solve() {
    n = sc.nextInt();
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] = sc.nextInt();
        }
    }
    dfs(0, 0);
    System.out.println(ans);
}
 
public static void dfs(int v, int len) {
    if (n / 2 == len) {
        divideTeam();
    } else {
        for (int i = v + 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, len + 1);
            }
        }
    }
    // backtracking
    visited[v] = false;
}
 
public static void divideTeam() {
    int[] a = new int[n / 2 + 1];
    int[] b = new int[n / 2 + 1];
    int ai = 1, bi = 1;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) {
            a[ai++] = i;
        } else {
            b[bi++] = i;
        }
    }
 
    int aStat = getStat(a);
    int bStat = getStat(b);
    int diff = Math.abs(aStat - bStat);
 
    if (ans > diff) {
        ans = diff;
    }
}
 
public static int getStat(int[] array) {
    int result = 0;
    int len = n / 2;
 
    for (int i = 1; i <= len; i++) {
        for (int j = i + 1; j <= len; j++) {
            result += map[array[i]][array[j]];
            result += map[array[j]][array[i]];
        }
    }
    return result;
}