[BOJ - JAVA] 14889 - 스타트와 링크(백트래킹)

# 주소

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

14889번: 스타트와 링크

 

# 문제

# 문제 해설 및 코드리뷰

import java.util.*;
public class Main{
	static int[][] arr;
	static int n;
	static boolean[] visit;
	static int sum[];
	static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        visit = new boolean[n];

        dfs(0,0);

        System.out.println(min);
    } 
    public static void dfs(int t, int p) {
    	if(p == n/2) {
    		diff();
    		return;
    	}

    	for(int i = t; i < n; i++) {
    		if(!visit[i]) {
    			visit[i] = true;
    			dfs(i+1, p+1);
    			visit[i] = false;
    		}
    	}
    }
    public static void diff() {
    	int team_start = 0;
    	int team_link = 0;
    	for(int i = 0; i < n-1; i++) {
    		for(int j = i+1; j < n; j++) {
    			if(visit[i] == true && visit[j] == true) {
    				team_start += arr[i][j];
    				team_start += arr[j][i];
    			}
    			else if(visit[i] == false && visit[j] == false) {
    				team_link += arr[i][j];
    				team_link += arr[j][i];
    			}
    		}
    	}
    	int val = Math.abs(team_start - team_link);

    	if(val == 0) {
    		System.out.println(val);
    		System.exit(0);
    	}
    	min = Math.min(val, min);
    }
}

처음에는 arr[i][j] + arr[j][i]를 dp[k]에 담으려고 했습니다.

이떄 k는 두 arr의 합을 저장하면 되므로 nC2입니다 따라서 만약 n이 4라면 k = 6, n이 6이라면 k = 15, n이 8이라면 k = 28개 크기의 인덱스의 dp를 만들 수 있습니다.

하지만 n이 커질수록 들어가는 인덱스의 수가 늘어나므로 그 부분을 체크할 수 없어 조합을 이용해서 푸는 방식을 포기했습니다.

 

따라서 컴퓨팅적 사고로 풀어야 하는데, 이 문제는 백트래킹을 이용한 문제입니다.

먼저 arr를 2차원 크기로 입력 받습니다. 여기서 중요한 건, arr[i][j] 는 i와 j가 같을 때,

0	1	2	3
2	0	3	1
3	1	0	1
5	5	1	0

즉, 배열에서 우하향방향의 대각선에 있는 인덱스 값은 모두 0이 된다는 사실입니다.

그리고 백트래킹 문제이며 중복을 허용하지 않기 때문에 반드시 boolean타입의 visit을 선언합니다.

그리고 dfs(0,0);을 실행할 건데, dfs함수는 밑에서 정의하겠습니다.

public static void dfs(int t, int p){에서

t는 시작점, p는 인덱스입니다. 즉, p가 n/2가 될 때 diff함수를 실행합니다.

왜냐하면 자 n이 8이 입력되었을 때를 가정하겠습니다.

그럼 4개의 선수가 한 팀이 되어야 합니다. 따라서 p는 4가 되어야 합니다. 

이후 for문에서 백트래킹 구문을 입력해주고 diff함수를 정의합니다.

 

diff에서 team_start와 team_link를 각각 0으로 초기화합니다. 그리고 이중 if문을 이용하여 visit[i]와 visit[j]가 true인 곳(방문한 인덱스)은 team_start에 arr[i][j]와 arr[j][i]를 더해줍니다. 그리고 둘 다 false일 때에는 team_link에 각각 더해줍니다.(방문 안한 인덱스) 

이후, team_start - team_link를 뺸 값을 절댓값을 씌워 val에 저장합니다(거꾸로 해도됨)

그리고 만약 val == 0이될 때는 바로 출력을 하고 min에 val와 min을 비교하여 작은 값을 넣습니다.

이때 min은 max_value값이므로 가장 큰 정수입니다.

이렇게 작성하시고 제출 하면 원하는 출력값을 얻을 수 있을 것입니다.

감사합니다.