[JAVA]백준 17406번 배열 돌리기 4

📌문제 링크

---

https://www.acmicpc.net/problem/17406

📌문제 설명

---

깊은 복사를 주의하며 백트래킹에서 회전만 조심하면 되는 문제입니다. 배열 돌리기 1 문제에 백트래킹 개념만 추가되었습니다. https://gepetton.github.io/posts/No.16926/

📌코드

---

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

// 회전 정보 클래스
class RotateInfo {
    int r, c, s;
    RotateInfo(int r, int c, int s) {
        this.r = r;
        this.c = c;
        this.s = s;
    }
}

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, M, K;
    static int[][] map = new int[51][51];
    static Boolean[] visited = new Boolean[7];
    static ArrayList<RotateInfo> rotateList = new ArrayList<>();
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        input(); // 입력 받기
        solve(); // 문제 해결
    }

    // 입력을 받는 메서드
    public static void input() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            RotateInfo info = new RotateInfo(r, c, s);
            rotateList.add(info);
        }
        br.close();
    }

    // 회전 연산을 수행하는 메서드
    public static void rotate(int idx) {
        if (idx == K) {
            answer = Math.min(answer, getMin());
            return;
        }
        for (int i = 0; i < K; i++) { // rotateList 대신 인덱스로 ��회
            if (visited[i]) continue;
            visited[i] = true;

            // 회전 전에 원래 맵을 복사
            int[][] copyMap = new int[51][51];
            for (int x = 1; x <= N; x++) {
                for (int y = 1; y <= M; y++) {
                    copyMap[x][y] = map[x][y];
                }
            }

            // 회전 연산 수행
            RotateInfo rotateInfo = rotateList.get(i);
            int r = rotateInfo.r;
            int c = rotateInfo.c;
            int s = rotateInfo.s;
            for (int j = 1; j <= s; j++) {
                int sr = r - j;
                int sc = c - j;
                int er = r + j;
                int ec = c + j;
                int temp = map[sr][sc];
                for (int x = sr; x < er; x++) {
                    map[x][sc] = map[x + 1][sc];
                }
                for (int y = sc; y < ec; y++) {
                    map[er][y] = map[er][y + 1];
                }
                for (int x = er; x > sr; x--) {
                    map[x][ec] = map[x - 1][ec];
                }
                for (int y = ec; y > sc + 1; y--) {
                    map[sr][y] = map[sr][y - 1];
                }
                map[sr][sc + 1] = temp;
            }

            // 다음 회전 연산 수행
            rotate(idx + 1);

            // 백트래킹: 원래 맵 복원
            for (int x = 1; x <= N; x++) {
                for (int y = 1; y <= M; y++) {
                    map[x][y] = copyMap[x][y];
                }
            }

            visited[i] = false;
        }
    }

    // 최소 값을 구하는 메서드
    public static int getMin() {
        int mn = Integer.MAX_VALUE;
        for (int i = 1; i <= N; i++) {
            int sum = 0;
            for (int j = 1; j <= M; j++) {
                sum += map[i][j];
            }
            mn = Math.min(mn, sum);
        }
        return mn;
    }

    // 문제를 해결하는 메서드
    public static void solve() {
        for (int i = 0; i < 7; i++) {
            visited[i] = false;
        }
        rotate(0);
        System.out.println(answer);
    }
}