[백준14889번] 스타트와 링크

문제

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

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

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입력 1 복사

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력 1 복사

0

예제 입력 2 복사

6
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

예제 출력 2 복사

2

예제 입력 3 복사

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

예제 출력 3 복사

1

나의 풀이

백트래킹으로 우선 두 팀으로 나누는 과정을 통해 팀이 모두 나뉘면 두 팀간의 능력치 차이를 구해서 min값을 최신화 시키면 되었다. 문제는 그렇게 어렵지 않았지만 계속 시간초과가 나서 고생을 했다... 알고보니 백트래킹을 할때 for문 안에서 i를 넘겨야 하는데 인자로 받은 값에 +1을 한 값을 넘기고 있었다. 그래서 depth값을 만들고 for문안에서 재귀를 돌때 i값을 넘겨주니 시간초과가 나지않게 되었다. 또 여기서 중요한 점은 depth가 하나 증가하고 다음 재귀를 돌 때 중복을 피하기 위해서는 앞에서 넘겨받은 수보다 하나 큰 수부터 시작해야댄다는 것이다. 예를들면, (1,2,3) 이렇게 팀이 되었다고 하자. 그러면 이때는 처음 값이 1인것이고 다음에 재귀를 돌때는 2가 넘어가고 for문이 1부터 돈다면 (2,1,3) 이러한 팀이 생성이 될 것이다. 이러면 앞에서의 팀과 동일한 것이므로 중복이다. 따라서 이러한 경우를 피하기위해서는 2로 재귀를 돌기 시작할때 for문을 3부터 돈다면 (2,1)로 시작하는 팀은 생성될 수 없다.

이걸 모르고 처음에 ArrayList로 구현했다가 배열로 바꾸고 for문을 최소화 시켜보기도 하고 해보았지만 근본적인 저 문제때문에 계속 시간초과가 났었다.

이 문제의 핵심은 팀을 나누어서 어떻게 저장을 해놓을 것인지 예를들면 팀별로 ArrayList를 만들고 각 선수들의 번호를 넣어도되고, 아래 코드처럼 방문여부에 따라 두 선수 모두 방문을 했으면 start팀 두 선수 모두 방문하지 않은 상태면 link팀 이렇게 나누어도 된다.

자칫 쉬워보일 수 있는 문제였다. 필자가 그러했다... 그러나 시간초과로 너무 고생을 해서 조금은 까다로운 문제였다고 생각한다...ㅎㅎ

코드

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

/**
 * 14889번 스타트와 링크
 */
public class Baeckjun14889 {
    static boolean[] player;    // 방문여부를 확인하기 위한 배열
    static int n;
    static int[][] status;
    static int min = 2000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        player = new boolean[n+1];
        status = new int[n+1][n+1];

        StringTokenizer st = null;
        for (int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=1; j<=n; j++) {
                status[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        devide(1,0);

        System.out.println(min);
    }

    static void devide(int num, int depth) {
        if (depth == n/2) {
            addStatus();
            return;
        }
        for (int i=num+1; i<=n; i++) {
            if (!player[i]) {
                player[i] = true;
                devide(i,depth+1);
                player[i] = false;
            }
        }
    }

    static void addStatus() {
        int startAllStatus = 0;
        int linkAllStatus = 0;

        for (int i=1; i<=n; i++) {
            for (int j=i+1; j<=n; j++) {
                if(player[i] && player[j])
                    startAllStatus += (status[i][j] + status[j][i]);
                else if(!player[i] && !player[j])
                    linkAllStatus += (status[i][j] + status[j][i]);
            }
        }

        int diff = Math.abs(startAllStatus-linkAllStatus);
        if (min > diff) min = diff;
    }
}