[Algorithm/Java] SWEA 4881번 - 배열 최소 합

---

배열 최소 합

---

🔍 문제 풀이

문제 도식화

💻 코드

전체 코드

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

public class Solution {
    static int n, ans;
    static int[][] arr;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];
            visited = new boolean[n];
            ans = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dfs(0, 0);
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void dfs(int depth, int sum) {
        // 1. 가지치기
        if (sum >= ans) return; // 현재 값이 최솟값 이상이면 중단

        // 2. 종료조건
        if(depth == n){
            ans = Math.min(sum, ans);
            return;
        }

        // 3. 모든 열 탐색 (백트래킹)
        for(int j=0; j<n; j++){
            if(!visited[j]){
                visited[j] = true;
                dfs(depth + 1, sum + arr[depth][j]); // 누적합, 다음 행으로
                visited[j] = false;
            }
        }
    }
}

스켈레톤 코드

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

public class Solution {
    static int n, ans;
    static int[][] arr;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];
            visited = new boolean[n];
            ans = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dfs();
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void dfs() {

    }
}