[백준] 배열 돌리기 4 (JAVA)

배열 돌리기 4_17406

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

17406번: 배열 돌리기 4

문제 설명

NxM크기의 배열이 주어지고

회전을 시행할 명령어 r,c,s가 주어진다.

이는 (r-s,c-s) 좌표를 왼쪽 상단 모서리로하고 (r+s,c+s)좌표를 오른쪽 하단 모서리로하는

사각형 만큼 시계방향으로 회전을 하라는 의미이다.

 

예를들어 배열의 크기가 6x6이고 rcs가 (3,4,2)인 경우는 아래와 같이 회전한다.

최종적으로 구해야하는 값은 

이 회전시킨 배열에서 각행의 합중에서 최솟값이다.

 

1 8 2   =>11
3 8 2   =>13
3 4 3   =>10
위와 같은 배열의 경우에는 최솟값은 10이다.

 

그런데 이 r,c,s가 여러개 주어질 수 있다.

그리고 이 회전의 순서는 자유롭게 변경할 수 있다.

회전을 어떻게 하느냐에 따라 나오는 배열이 달라질 수 있다.

 

회전의 순서를 자유롭게 설정하여 구할 수 있는 최솟값을 구하는 문제이다.

---

문제 풀이

생각 과정

r,c,s를 배열로 선언해서 입력받을 때 미리 저장해두고

이를 통해 브루트포스로 모든 회전의 경우를 구하는 방식을 생각했다.

 dfs를 통해 구현을 했고 각 기능들을 메서드화 하였다.

 

회전하는 메서드는 

위 그림처럼 바깥에서부터 한줄씩 돌리는 것으로 구현했다.

구현

public class 배열돌리기4_17406 {
    static int N, M, K, answer;
    static int[][] arr, rcs;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NMK = br.readLine().split(" ");
        N = Integer.parseInt(NMK[0]);
        M = Integer.parseInt(NMK[1]);
        K = Integer.parseInt(NMK[2]);
        arr = new int[N][M];
        visit = new boolean[K];
        rcs = new int[K][3];
        answer = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(row[j]);
            }
        }
        for (int i = 0; i < K; i++) {
            String[] str = br.readLine().split(" ");
            rcs[i][0] = Integer.parseInt(str[0]) - 1; // r (인덱스로 사용하기위해 -1)
            rcs[i][1] = Integer.parseInt(str[1]) - 1; // c (인덱스로 사용하기위해 -1)
            rcs[i][2] = Integer.parseInt(str[2]); // s
        }
        int[][] copy = copy(arr);
        dfs(0, copy);
        System.out.println(answer);
    }
    public static int[][] copy(int[][] arr){    // 배열을 복사하는 메서드
        int[][] result = new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            result[i] = arr[i].clone();
        }
        return result;
    }

    public static void dfs(int cur, int[][] copy) { // 재귀를 통해 모든 순서확인
        if (cur == K) {
            answer = Math.min(answer, cal(copy));
            return;
        }
        for (int i = 0; i < K; i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(cur + 1, go(rcs[i][0], rcs[i][1], rcs[i][2], copy(copy)));
                visit[i] = false;
            }
        }
    }

    public static int cal(int[][] array) {  // 각 행의 합을 구해 최솟값을 구하는 메서드
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            int sum = 0;
            for (int j = 0; j < array[0].length; j++) {
                sum += array[i][j];
            }
            min = Math.min(min, sum);
        }
        return min;
    }

    public static int[][] go(int r, int c, int s, int[][] copied) { // 회전을 시작하는 메서드(바깥쪽부터 안쪽으로)
        for (int i = 0; i < s; i++) {
            copied = rotate(r - s + i, c - s + i, (s-i)*2, copied);
        }
        return copied;
    }

    public static int[][] rotate(int y, int x, int c, int[][] array) {  // 회전 메서드(한줄씩)
        int temp = array[y][x + c];
        for (int i = 0; i < c; i++) {   // 상단
            array[y][x + c - i] = array[y][x + c - i - 1];
        }
        for (int i = 0; i < c; i++) {   // 좌측
            array[y + i][x] = array[y + i + 1][x];
        }
        for (int i = 0; i < c; i++) {   // 하단
            array[y + c][x + i] = array[y + c][x + i + 1];
        }
        for (int i = 0; i < c - 1; i++) {   // 우측
            array[y + c - i][x + c] = array[y + c - i - 1][x + c];
        }
        array[y+1][x + c] = temp;
        return array;
    }
}

 

주의점

자바에선 배열을 복사하면 얕은 복사가 되어 주소값이 복사가 된다.

그래서 clone() 메서드를 사용하여 깊은 복사를 했는데

이중 배열은 clone()메서드를 사용하면 외부 배열은 깊은 복사가 되나, 내부 배열은 얕은 복사가 된다.

따라서 copy()메서드를 새로 만들어서 내부 배열까지 깊은 복사를 하도록 구현을 해줬다.