[JAVA 47일차 / 하루 3문제] 2580번, 14888번, 14889번

1. 2580번 스도쿠

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] board = new int[9][9];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 받기
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solve(0, 0);
    }

    static void solve(int row, int col) {
        if (col == 9) {
            solve(row + 1, 0);
            return;
        }

        if (row == 9) {
            printBoard();
            System.exit(0); // 답을 찾으면 바로 종료
        }

        if (board[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (isValid(row, col, i)) {
                    board[row][col] = i;
                    solve(row, col + 1);
                    board[row][col] = 0;
                }
            }
        } else {
            solve(row, col + 1);
        }
    }

    static boolean isValid(int row, int col, int num) {
        // 가로
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) return false;
        }
        // 세로
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) return false;
        }
        // 3x3
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == num) return false;
            }
        }
        return true;
    }

    static void printBoard() {
        StringBuilder sb = new StringBuilder();
        for (int[] row : board) {
            for (int num : row) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

• 백트래킹 : 가능한 경우의 수를 다 넣어보고 안되면 전으로 돌아가는 방법 ( 여기서는 solve 함수가 핵심 )
•     board[row][col] = 0;        이 부분을 지정해주는게 중요하다. 모든 경우의 수를 다 돌려보고 안되면 다시 처음으로 돌아가는 이 코드를 지정해야 진행하다가 안되는 경우의 수가 나왔을 때 이전 경우의 수로 돌아가야 한다.

---

2. 14888번 연산자 끼워넣기

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

public class Main {
    static int N;
    static int[] nums;
    static int[] ops = new int[4]; // +, -, *, /
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        nums = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            ops[i] = Integer.parseInt(st.nextToken()); // 연산자 개수 입력
        }

        dfs(1, nums[0]); // 첫 숫자는 고정, index=1부터 시작
        System.out.println(max);
        System.out.println(min);
    }

    static void dfs(int idx, int result) {
        if (idx == N) { // 모든 숫자 다 사용했으면
            max = Math.max(max, result);
            min = Math.min(min, result);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (ops[i] > 0) {
                ops[i]--; // 연산자 하나 사용

                int next = result;
                if (i == 0) next += nums[idx];
                else if (i == 1) next -= nums[idx];
                else if (i == 2) next *= nums[idx];
                else if (i == 3) next /= nums[idx];

                dfs(idx + 1, next); // 다음 숫자와 계산된 값으로 재귀

                ops[i]++; // 연산자 복구 (백트래킹)
            }
        }
    }
}

nums = [1, 2, 3]
연산자: + 1개, * 1개


dfs(1, 1)  // result = 1에서 시작

// 첫 번째 경우: + 2
→ dfs(2, 3)

// 두 번째 경우: * 3
→ dfs(3, 9)
→ max = 9, min = 9

// 다른 경로: * 2
→ dfs(2, 2)
→ + 3
→ dfs(3, 5)
→ max = 9, min = 5

---

3. 14889번 스타트와 링크

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

public class Main {
    static int N;
    static int[][] S;
    static boolean[] selected;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        S = new int[N][N];
        selected = new boolean[N];

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

        // 조합 탐색 시작
        comb(0, 0);
        System.out.println(min);
    }

    static void comb(int idx, int count) {
        if (count == N / 2) {
            calc();
            return;
        }

        for (int i = idx; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                comb(i + 1, count + 1);
                selected[i] = false; // 백트래킹
            }
        }
    }

    static void calc() {
        int team1 = 0;
        int team2 = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (selected[i] && selected[j]) {
                    team1 += S[i][j];
                } else if (!selected[i] && !selected[j]) {
                    team2 += S[i][j];
                }
            }
        }

        int diff = Math.abs(team1 - team2);
        min = Math.min(min, diff);
    }
}