[BOJ] 16935 - 배열돌리기(JAVA)

문제

글이 길어서 링크로 대체합니다.
https://www.acmicpc.net/problem/16935

풀이

기본적인 풀이는 r번의 연산에 대해서 배열을 변환시키면서 진행하는 것입니다.
그러나, 이번 문제에서는 좀 더 어렵지만 빠르게 풀어보고 싶었고, 이를 위해서 선형대수의 행렬 연산과 관련된 이론을 적용했습니다.

기존의 방식은 nm크기의 배열을 r번 변환시키는 연산이 필요했지만, 최적화한 코드에서는 2*2 배열로 회전과 반전에 대한 정보를 저장합니다.
이를 통해서 nmr의 연산에서 약 4r+nm의 연산으로 줄일 수 있었고, r의 값이 커지면 커질수록 기존보다 빠른 속도로 결과를 알 수 있습니다.
회전/반전은 5,6번 연산인 4분할 영역 이동과 translation과 transformation으로 서로 다른 연산입니다.
이를 해결하기 위해서는 x,y의 좌표계에서 확장한 hormogeneous 좌표계를 사용할 수 있지만, 3*3 행렬로 연산량이 늘어나기 때문에, 회전과 반전에 대한 2*2 행렬을 연산하며 이에 따른 4분할 영역이 바뀌는 것을 따로 직접 연산해줬습니다.
이것이 가능한 이유는 전체 영역에서 회전/반전을 할 경우, 답이 달라지지만, 4분할 영역 내에서 회전/반전을 할 경우에는 결과값이 동일하기 때문입니다.

4분할 영역은 좀 더 직관적으로 보기 위해
1 | 2
-----
3 | 4 이러한 형태로 치환하여 생각했습니다.

코드

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


public class Main {

    static int[] subArr = {0,1,2,3};
    static int[][][] splitArr = new int[4][][];
    static int[][] tfArr = {{1,0},{0,1}};
    static int[][][] answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(br.readLine());
        int n=Integer.parseInt(tk.nextToken());
        int m=Integer.parseInt(tk.nextToken());
        int r=Integer.parseInt(tk.nextToken());
        int[][] temp;

        int[][] arr = new int[n][m];
        for(int i=0; i<4; i++)
            splitArr[i] = new int[n/2][m/2];
        int subN = n/2;
        int subM = m/2;
        for(int y=0; y<n; y++) {
            tk = new StringTokenizer(br.readLine());
            int subY = y/subN;
            for(int x=0;x<m;x++) {
                int subX = x/subM;
                splitArr[2*subY + subX][y%subN][x%subM] = Integer.parseInt(tk.nextToken());
                arr[y][x] = splitArr[2*subY + subX][y%subN][x%subM];
            }
        }     
        tk = new StringTokenizer(br.readLine());
        for(int i=0; i<r; i++) {
            int cmd = Integer.parseInt(tk.nextToken());
            switch(cmd) {
            case 1:
                temp = splitArr[0];
                splitArr[0] = splitArr[2];
                splitArr[2] = temp;
                temp = splitArr[1];
                splitArr[1] = splitArr[3];
                splitArr[3] = temp;
                tfArr = new int[][] {{tfArr[0][0],tfArr[0][1]},{-tfArr[1][0],-tfArr[1][1]}};
                break;
            case 2:
                temp = splitArr[0];
                splitArr[0] = splitArr[1];
                splitArr[1] = temp;
                temp = splitArr[2];
                splitArr[2] = splitArr[3];
                splitArr[3] = temp;
                tfArr = new int[][] {{-tfArr[0][0],-tfArr[0][1]},{tfArr[1][0],tfArr[1][1]}};
                break;
            case 3:
                tfArr = new int[][] {{-tfArr[1][0],-tfArr[1][1]},{tfArr[0][0],tfArr[0][1]}};
            case 5:
                temp = splitArr[3];
                splitArr[3] = splitArr[1];
                splitArr[1] = splitArr[0];
                splitArr[0] = splitArr[2];
                splitArr[2] = temp;
                break;
            case 4:
                tfArr = new int[][] {{tfArr[1][0],tfArr[1][1]},{-tfArr[0][0],-tfArr[0][1]}};
            case 6:
                temp = splitArr[0];
                splitArr[0] = splitArr[1];
                splitArr[1] = splitArr[3];
                splitArr[3] = splitArr[2];
                splitArr[2] = temp;
                break;
            }
        }
        int totalX = tfArr[0][0]*subM + tfArr[0][1]*subN;
        int totalY = tfArr[1][0]*subM + tfArr[1][1]*subN;
        int newX = Math.min(-1, totalX);
        int newY = Math.min(-1, totalY);
        totalX = Math.abs(totalX);
        totalY = Math.abs(totalY);
        answer = new int[4][totalY][totalX];

        for(int i=0; i<4; i++) {
            for(int y=0; y<subN; y++) {
                for(int x=0; x<subM; x++) {
                    int nx = tfArr[0][0]*x + tfArr[0][1]*y-newX-1;
                    int ny = tfArr[1][0]*x + tfArr[1][1]*y-newY-1;
                    answer[i][ny][nx] = splitArr[i][y][x];
                }
            }
        }
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<totalY; i++){
            for(int num:answer[0][i]){
                sb.append(num).append(' ');
            }
            for(int num:answer[1][i]){
                sb.append(num).append(' ');
            }
            sb.append('\n');
        }
        for(int i=0; i<totalY; i++){
            for(int num:answer[2][i]){
                sb.append(num).append(' ');
            }
            for(int num:answer[3][i]){
                sb.append(num).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb.toString());
    }

}

결과

반전과 회전도 2x2 연산을 하지 않고 마지막에 만들어서 최적화한다면 좀 더 빨라질 수 있겠지만 그래도 java기준 실행시간 5위를 찍었다!