[백준 17406] - 배열돌리기4(JAVA)[골드4]

문제

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

17406번: 배열 돌리기 4

 

문제 풀이

앞선 배열 돌리기 2와 비슷한 문제이다.

거기에선 배열의 원소들을 반시계 방향으로 움직였다면, 이번 문제는 시계방향으로 움직이는 것이다.

그 외에 추가된 것은 연산의 순서를 생각하는 것이다.

회전의 순서에 따라서 배열의 모양이 다르기 때문에 조합이 아닌 순열을 통해서 경우의 수를 산출하고, 회전을 했다.

껍데기의 수는 입력에서 받은 s로 결정하고, r과 c를 통해서 사각형의 꼭짓점 경계를 삼아서 영역을 제한했다.

 

문제를 풀면서 했던 실수로는 한 번의 순열 조합으로 회전을 한 뒤, 입력받은 배열을 기준으로 다음 경우의 수를 적용해야 했다.

그 과정에서 graph = origin;이라는 코드를 통해서 원본 배열을 적용하는 코드를 작성했는데,

자바에서 이렇게 코드를 작성할 경우 얕은 복사를 통해서 graph가 바뀔 경우 origin도 같이 바뀌는 현상이 일어났고,

문제를 통과하지 못했다.

배열을 깊은 복사하는 여러 방법이 있겠지만, 아직 자바에 미숙하지 않아서 n*m의 반복문으로 하나하나 배열을 옮겨줬다.

clone이라는 방법도 있지만, 아직 익숙하지 않은 것 같다.

 

전체 코드

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

public class Main {

    static int n;
    static int m;
    static int k;
    static int r;
    static int c;
    static int s;
    static BufferedReader br;
    static StringTokenizer st;
    static int[][] graph;
    static Rotate[] rotate;
    static int[] comb;
    static int[][] temp;
    static boolean[] visit;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        combination(k, 0, 0);
        System.out.print(answer);
    }

    public static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        graph = new int[n][m];
        rotate = new Rotate[k];
        temp = new int[n][m];
        visit = new boolean[k];
        comb = new int[k];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            r = Integer.parseInt(st.nextToken()) - 1;
            c = Integer.parseInt(st.nextToken()) - 1;
            s = Integer.parseInt(st.nextToken());
            rotate[i] = new Rotate(r, c, s);
        }
    }

    public static void combination(int limit, int count, int cur) {
        if (limit == count) { // 조합 뽑앗을때 돌리기
            doRotate();
            return;
        }
        for (int i = 0; i < k; i++) {
            if (!visit[i]) {
                comb[count] = i;
                visit[i] = true;
                combination(limit, count + 1, i);
                visit[i]= false;
            }
        }
    }


    public static void doRotate() {
        copy();
        for (int tc = 0; tc < k; tc++) {
            Rotate now = rotate[comb[tc]]; // 현재 회전 정보
            int r = now.r;
            int c = now.c;
            int S = now.s;
            for (int s = 1; s <= S; s++) {
                // 위
                int upTmp = temp[r - s][c + s];
                for (int y = c + s; y > c - s; y--) {
                    temp[r - s][y] = temp[r - s][y - 1];
                }
                // 오른쪽
                int rightTmp = temp[r + s][c + s];
                for (int x = r + s; x > r - s; x--) {
                    temp[x][c + s] = temp[x - 1][c + s];
                }
                temp[r - s + 1][c + s] = upTmp;
                // 아래
                int leftTmp = temp[r + s][c - s];
                for (int y = c - s; y < c + s; y++) {
                    temp[r + s][y] = temp[r + s][y + 1];
                }
                temp[r + s][c + s - 1] = rightTmp;
                // 왼쪽
                for (int x = r - s; x < r + s; x++) {
                    temp[x][c - s] = temp[x + 1][c - s];
                }
                temp[r + s - 1][c - s] = leftTmp;
            }
        }
        getSum(temp);
    }
    public static void copy() {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                temp[i][j] = graph[i][j];
            }
        }
    }

    public static void getSum(int [][] temp) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = 0;
            for (int j = 0; j < m; j++) {
                sum += temp[i][j];
            }
            answer = Math.min(answer, sum);
        }
    }

    static class Rotate {
        int r;
        int s;
        int c;

        public Rotate(int r, int c, int s) {
            this.r = r;
            this.c = c;
            this.s = s;
        }
    }
}