[백준] 14889번 스타트와 링크 - Java, 자바

난이도

실버 2

문제

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

풀이

백트래킹으로 문제를 해결했다.

1. 팀조합을 만든다. (한 팀의 인원수는 n/2)
   for문을 실행해 방문하지 않은 팀원이면 방문하고 백트래킹 수행 재귀가 끝나면 비방문으로 변경
   
   
   여기 반복문에서 i=0으로 할경우 시간초과가 나온다. 경우를 잘 따지고 순열이 아닌 조합일 땐,
   i=idx로 해서 가지치기를 수행하여 시간을 절약해야한다.

   
   	for(int i = idx; i < N; i++) {
   		// 방문하지 않았다면?
   		if(!visit[i]) {
   			visit[i] = true;	// 방문으로 변경
   			combi(i + 1, count + 1);	// 재귀 호출
   			visit[i] = false;	// 재귀가 끝나면 비방문으로 변경
   		}
   	}

2. 팀조합이 완성된 경우 팀 당 능력치의 합을 구해서 최솟값을 찾는다.

	static void diff() {
        int start = 0;
        int link = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i; j < n; j++) {
                if (visit[i] == true && visit[j] == true) {
                    start += map[i][j];
                    start += map[j][i];
                } else if (visit[i] == false && visit[j] == false) {
                    link += map[i][j];
                    link += map[j][i];
                }
            }
        }

        int val = Math.abs(start - link);
        min = Math.min(val, min);
    }

코드

코드1)

package 백트래킹;

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

public class BOJ14889 {
   static int n;
   static int[][] map;
   static int min = Integer.MAX_VALUE;
   static boolean[] visit;

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

       n = Integer.parseInt(br.readLine());

       map = new int[n][n];

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

       visit = new boolean[n];
       back(0, 0);
       System.out.println(min);


   }

   static void back(int idx, int depth) {
       if (depth == n/2) {
           diff();
           return;
       }

       for (int i = idx; i < n; i++) { //
           if (!visit[i]) {
               visit[i] = true;
               back(i + 1, depth + 1);
               visit[i] = false;
           }
       }
   }

   static void diff() {
       int start = 0;
       int link = 0;
       for (int i = 0; i < n - 1; i++) {
           for (int j = i; j < n; j++) {
               if (visit[i] == true && visit[j] == true) {
                   start += map[i][j];
                   start += map[j][i];
               } else if (visit[i] == false && visit[j] == false) {
                   link += map[i][j];
                   link += map[j][i];
               }
           }
       }

       int val = Math.abs(start - link);
       min = Math.min(val, min);
   }


}

코드2)
능력치 구하는 부분이 조금 다르지만 같은 의미이다.
코드 1보다 복잡하지만 직관적이다.

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

public class BOJ14889 {
	static int n;
	static int[][] map;
	static int min = Integer.MAX_VALUE;
	static boolean[] visit;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());

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

		back(0,0);
		System.out.println(min);

	}

	private static void back(int depth,int start) {
		// TODO Auto-generated method stub
		if (depth == n / 2) {
			int[] arr = new int[n / 2];
			int[] arr2 = new int[n / 2];
			int j = 0, k = 0;
			for (int i = 0; i < n; i++) {
				if (visit[i]) {
					arr[j++] = i;
				} else {
					arr2[k++] = i;
				}
			}

			int s = start(arr);

			int l = link(arr2);

			min = Math.min(min, Math.abs(s - l));
			return;

		}

		for (int i = start; i < n; i++) {
			if (!visit[i]) {
				visit[i] = true;
				back(depth + 1,i+1);
				visit[i] = false;

			}
		}

	}

	private static int start(int[] start) {

		int sum = 0;
		for (int i = 0; i < start.length; i++) {
			for (int j = 0; j < start.length; j++) {
				if (i == j)
					continue;
				int x = start[i];
				int y = start[j];
				sum += map[x][y];

			}
		}
		return sum;
	}

	private static int link(int[] link) {

		int sum = 0;
		for (int i = 0; i < link.length; i++) {
			for (int j = 0; j < link.length; j++) {
				if (i == j)
					continue;
				int x = link[i];
				int y = link[j];
				sum += map[x][y];

			}
		}

		return sum;
	}

}