[BOJ_14889 | DFS & BackTracking] 스타트와 링크

풀이

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

DFS 백트래킹에 관한 간단한 문제였는데, 백트래킹이란, 모든 경우의 수를 모두 고려하는 알고리즘으로써,

위 주어진 문제와 같이 팀을 나눌 수 있는 모든 경우의 수를 고려하는 데에 적합하다.

우선 DFS함수를 0~n/2 - 1 에 해당하는 Vertex에서 실행한다.

절반만 돌리는 이유는 순열이 아니라 조합을 구하는 문제이기 때문에 

어차피 한 팀을 구하면 나머지 팀이 자동으로 결정되기 때문에 시간낭비를 막기 위한 처리였다.

예를 들어

0에서 시작한 DFS는 우선 점을 하나 방문했으므로 isVisit[0] = true로 바꿔주고 

방문한 점의 개수를 나타내는 len의 길이를 1 증가시켜 준다.

len == n/2인 경우 하나의 조가 짜여진 경우이므로 팀을 나누어 능력치를 계산한 후

최솟값을 갱신해 준다.

한 번의 DFS가 끝난 후에는 다시 isVisit의 값을 false로 바꾸어 다른 점을 방문할 수 있게 만들어 준다.

굳이 Buffer를 쓰지 않고 Scanner를 쓰고도 시간초과를 내지 않는 문제였던 것 같다.

소스 코드

import java.util.*;
public class BOJ_14889 {
 
    static boolean[] isVisit;
    static int[][] map;
    static int min, n;
 
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        map = new int[n][n];
        isVisit = new boolean[n];
 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                map[i][j] = input.nextInt();
            }
        }
        min = Integer.MAX_VALUE;
        for(int i=0;i<n/2;i++){
            DFS(i, 0);
        }
        System.out.println(min);
 
    }
    public static void DFS(int edge, int len){
        len++; isVisit[edge] = true;
        if(len == n/2) divide();
        for(int i = edge+1;i<n;i++){
            DFS(i, len);
        }
        isVisit[edge] = false;
 
    }
    public static void divide(){
        int[] start = new int[n/2];
        int[] link = new int[n/2];
        int startN = 0; int linkN = 0;
        for(int i=0;i<n;i++){
            if(isVisit[i]) start[startN++] = i;
            else link[linkN++] = i;
        }
        abilityCal(start, link);
    }
    public static void abilityCal(int[] start, int[] link){
        int startVal = 0; int linkVal = 0;
        for(int i=0;i<n/2;i++){
            for(int j=i;j<n/2;j++){
                if(i!=j){
                    startVal += map[start[i]][start[j]];
                    startVal += map[start[j]][start[i]];
                    linkVal += map[link[i]][link[j]];
                    linkVal += map[link[j]][link[i]];
                }
            }
        }
        if(min > Math.abs(startVal-linkVal)) min = Math.abs(startVal-linkVal);
    }
}