백준 - 15661 링크와 스타트(Java)

 

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

 

백트랙킹(Backtracking) 문제 입니다.

백트랙킹이란, 탐색을 하면서 조건에 맞지 않는 부분을 가지치기하여 탐색의 범위를 줄이는 방법입니다.

그렇기 때문에 완전 탐색에 비해 메모리 및 시간에 이점이 있습니다.

 

이 문제에 두 가지 팀이 있으며, 2차원 배열이 주어졌을 때 두 팀간의 격차를 구하는 문제입니다.

2차원 배열 안에 적혀져 있는 값들은 행과 열의 숫자가 같은 팀이 되었을 때 팀이 얻는 점수입니다.

위 그림을 바탕으로 설명해 보겠습니다.

1번과 2번이 같은 팀을 하면 (1, 2)의 값과 (2, 1)의 합인 5가 팀의 점수가 되고,

반대 편의 팀은 3번과 4번 이므로 (3, 4)와 (4, 3)의 합인 7이 팀의 점수가 됩니다.

 

이제 어떻게 풀어야 할 지에 대해 설명 하겠습니다.

조합(Combination)만 만들 줄 안다면 아주 간단합니다.(순열과 조합할 때 그 조합입니다.)

N이 주어지면 1부터 N까지가 있다는 뜻이고,

이를 1 ~ N-1개 까지의 조합을 만들면 됩니다.(문제 조건에 의해 한 팀은 최소 한명이 있어야 합니다.)

 

N이 4가 주어진다고 예를 들어 보겠습니다.

그러면 한 개의 팀은 [{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}]으로 이루어 질 수 있습니다. 그러면 저절로 나머지는 다른 팀이 됩니다.

스타트 팀과 링크 팀이 있다고 하겠습니다.

1번만이 스타트 팀이면 2, 3, 4는 자동적으로 링크 팀입니다.

 

[구현 코드]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int n, ans;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            stz = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());
            }
        }

        ans = Integer.MAX_VALUE;

        boolean[] visited = new boolean[n];

        // 한 가지 조합을 만들고 해당 조합에 포함되면 start팀
        // 포함되지 않으면 link팀이라 판단하여 계산함
        for(int i=1; i<n; i++) {
            // i만큼
            backtracking(visited, i, 0);
        }

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void backtracking(boolean[] visited, int r, int depth) {
        // r 개 만큼 조합이 만들어 졌을 경우
        if(r==0){
            int startTeam = 0;
            int linkTeam = 0;

            for(int i=0; i<n; i++){
                if(visited[i]) {
                    // start팀에 포함되는 인원의 점수 합을 구함
                    for(int j=i+1; j<n; j++){
                        if(visited[j]){
                            startTeam += map[i][j];
                            startTeam += map[j][i];
                        }
                    }
                }else {
                    // link팀에 포함되는 인원의 점수 합을 구함
                    for(int j=i+1; j<n; j++){
                        if(!visited[j]){
                            linkTeam += map[i][j];
                            linkTeam += map[j][i];
                        }
                    }
                }
            }

            // 팀의 격차 최소를 갱신
            ans = Math.min(ans, Math.abs(startTeam - linkTeam));
            return;
        }
        if(depth==n){
            return;
        }

        // 현재 depth를 link 팀으로 뽑는다면
        visited[depth] = true;
        backtracking(visited, r-1, depth+1);

        // 현재 depth를 link 팀으로 뽑지 않는다면
        visited[depth] = false;
        backtracking(visited, r, depth+1);
    }
}