백준 - 백트래킹 14889번 스타트와 링크 / 풀이, 오답

= 내가 접근한 방법 =

처음 작성한 dfs 함수다.

이 메서드의 문제점은 2개까지는 구할 수 있어도 => n = 4일 때만 가능하고

n = 6일 때 부터 불가능했다.

n = 6일 때, 1-2-3 vs 4-5-6 이렇게 팀을 이루는 건데

내가 짠 함수로는 1-2, 3-4, 5-6 이런 식으로 진행이 되기 때문에 당연히 오답.

public static void dfs(int n, int depth) {
//        System.out.println("depth = " + depth);
        if (depth == n / 2) {
            for (int i = 0; i < depth; i++) {
                System.out.println("result: " + temp[i]);
            }
            int check = Math.abs(temp[0] - temp[1]);
            min = Math.min(min, check);
            return;
        }

        for (int i = 1; i <= n; i++) {
//            System.out.println("이 i값이 중요함 = " + i);
            if (visit2[i]) continue;
            for (int j = 1; j <= n; j++) {
                if (visit2[j]) continue;
                if (!visit[i][j]) {
                    System.out.println("i = " + i);
                    System.out.println("j = " + j);
                    System.out.println("==============");
                    temp[depth] += arr[i][j] + arr[j][i];
                    visit2[i] = true;
                    visit2[j] = true;

                    dfs(n, depth + 1);
                    temp[depth] = 0;
                    visit2[i] = false;
                    visit2[j] = false;
                }
            }
        }
    }

그럼 어떻게 해야 이 문제를 해결할 수 있을까?

1. n명 선수들이 주어지고, 우리가 구해야 되는 값은 n / 2명으로 이루어진 사람들의 능력치다. depth 조건을 설정한다.

2. 팀의 능력치를 2차원 배열을 이용해서 만든다.
3. visit 1차원 배열을 이용해서 방문 여부를 체크한다.
4. 방문 한 값과, 방문하지 않은 값을 => start, end로 나누고 두 값을 비교한다.

depth값을 이용해서, 방문 여부를 잘 체크하고
방문한 값과 방문하지 않은 값을 이용해서 start팀, link팀을 나눌 수 있다.
처음 접했을 때 어려웠지만 다른 풀이를 보고 익혀서 어떤 식으로 접근해야 하는지 알 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static int min = Integer.MAX_VALUE;
    public static int[][] arr;
    public static boolean[] visit;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];
        visit = new boolean[n + 1];
 
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        dfs(1, 0);
 
        System.out.println("min = " + min);
 
    }
 
    public static void dfs(int now, int depth) {
        if (depth == n / 2) {
            check();
            return;
        }
 
        for (int i = now; i <= n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(i + 1, depth + 1);
                visit[i] = false;
            }
        }
    }
 
    public static void check() {
        int start = 0;
        int end = 0;
 
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (visit[i] && visit[j]) {
                    start += (arr[i][j] + arr[j][i]);
                    System.out.println("i = " + i);
                    System.out.println("j = " + j);
                }
 
                if (!visit[i] && !visit[j]) {
                    end += (arr[i][j] + arr[j][i]);
                }
            }
        }
        int value = Math.abs(start - end);
        min = Math.min(min, value);
    }
}