코드트리_수들의 합 최대화하기

Main.java

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[][] grid;
    static boolean[] rowVisited;
    static boolean[] colVisited;
    static int answer;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
        rowVisited = new boolean[n];
        colVisited = new boolean[n];

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

        choose(0, 0);
        sb.append(answer);
        
        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    private static void choose(int cur, int sum) {
        if (cur == n) {
            answer = Math.max(answer, sum);
            return;
        }

        for (int j=0; j<n; j++) {
            if (colVisited[j]) {
                continue;
            }

            colVisited[j] = true;

            choose(cur + 1, sum + grid[cur][j]);

            colVisited[j] = false;
        }
    }
}