BOJ 14889 스타트와 링크

문제 풀이 방식

• DFS를 통한 백트랙킹 : 방문 여부 검사
• BF로 모든 경우의 수 탐색

문제 풀이 (Java)

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    static int N;
    static int[][] stat;
    static int minimum = 100000;
    static boolean[] visited;

    public static void main(String[] args) {
        N = scanner.nextInt();
        scanner.nextLine();
        stat = new int[N][N];
        visited = new boolean[N + 1];

        for (int i = 0; i < N; i++) {
            String[] input = scanner.nextLine().split(" ");
            for (int j = 0; j < N; j++) {
                stat[i][j] = Integer.parseInt(input[j]);
            }
        }

        DFS(0, 0);
        System.out.println(minimum);
    }

    static void DFS(int D, int idx) {
        if (D == (N / 2)) {
            int S = 0, L = 0;
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (visited[i] && visited[j]) {
                        S += (stat[i][j] + stat[j][i]);
                    } else if (!visited[i] && !visited[j]) {
                        L += (stat[i][j] + stat[j][i]);
                    }
                }
            }
            minimum = Math.min(minimum, Math.abs(S - L));
        }

        for (int i = idx; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                DFS(D + 1, i + 1);
                visited[i] = false;
            }
        }
    }
}