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

[백준]17406:배열 돌리기4

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

풀이

회전 순서에 따라 결과가 바뀌므로 순열을 사용하였다. 순열로 K의 회전 순서를 뽑은 후 회전시켰고, 회전이 끝난 후 각 배열의 행의 최솟값을 계산해주었다.

 

순열은 어렵지 않았지만 회전하는 부분이 생각해주어야 할 조건이 많아서 시간이 오래걸렸다.

회전을 하기 위해 한  자리씩 이동할 때 회전 방향에 존재하는 가장 마지막 값들이 지위져 이 값들을 따로 저장해준 후 마지막에 값을 변경해 주었다.

 

예를 들어 아래와 같은 경우이다.

0, 0	0, 1	0, 2	0, 3
1, 0	1, 1	1, 2	1, 3
2, 0	2, 1	2, 2	2, 3

위 테이블의 첫번째 행을 오른쪽으로 회전시키면

0, 0	0, 0	0, 1	0, 2
1, 0	1, 1	1, 2	1, 3
2, 0	2, 1	2, 2	2, 3

이와 같이 변경되고 0,3에 해당하는 값이 지워진다. 

마찬가지로 맨 오른쪽 열을 아래로 회전시키면

0, 0	0, 0	0, 1	0, 2
1, 0	1, 1	1, 2	0, 2
2, 0	2, 1	2, 2	1, 3

이번엔 2,3에 해당하는 값이 지워졌다. 그리고 0,2 자리는 앞에서 지워졌던 0,3이 들어가야한다.

이때 0,3을 보관해 두었다가 회전시킨 마지막 위치에 넣어주면 된다.

0, 0	0, 0	0, 1	0, 2
1, 0	1, 1	1, 2	0, 3
2, 0	2, 1	2, 2	1, 3

이런식으로 회전을 진행하였다.

 

이때 저장해 주어야 하는 값들의 규칙이 보인다. 바로 초기 배열의 모서리에 해당하는 부분이 된다. 따라서 배열을 만들어서 이러한 값들을 저장해 준 다음 오른쪽, 아래, 왼쪽, 위쪽으로 순서대로 회전시키며 적절한 위치에 해당 값을 입력해 주었다. 

 

 

코드

import java.util.*;
 
public class Main {
    
    static int[][] board;
    static int[][] rotation;
    static int min = Integer.MAX_VALUE;
    static int n, m;
    static boolean[] visited;
    static int[] result;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        int k = scan.nextInt();
        
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        
        rotation = new int[k][3];
        for(int i = 0; i < k; i++) {
            rotation[i][0] = scan.nextInt();
            rotation[i][1] = scan.nextInt();
            rotation[i][2] = scan.nextInt();
        }
        
        visited = new boolean[k];
        result = new int[k];
        permutation(0, k);
        
        System.out.println(min);
    }    
    
    public static void permutation(int idx, int k) {
        if(idx == k) {
            int[][] copy = new int[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    copy[i][j] = board[i][j];
                }
            }
            findMin(copy);
            return;
        }
        
        for(int i = 0; i < k; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                result[idx] = i;
                permutation(idx + 1, k);
                visited[i] = false;
            }
        }
    }
    
    public static void findMin(int[][] copy) {
        for(int i = 0; i < result.length; i++) {
            int lx = rotation[result[i]][0] - rotation[result[i]][2] - 1;
            int ly = rotation[result[i]][1] - rotation[result[i]][2] - 1;
            int rx = rotation[result[i]][0] + rotation[result[i]][2] - 1;
            int ry = rotation[result[i]][1] + rotation[result[i]][2] - 1;
            rotate(lx, ly, rx, ry, copy); //lx ly ~ rx ry까지 회전
        }
        rowcal(copy);//회전한 배열의 최소 행값을 구함
    }
    
    public static void rowcal(int[][] copy) {
        for(int i = 0; i < copy.length; i++) {
            int sum = 0;
            for(int j = 0; j < copy[i].length; j++) {
                sum += copy[i][j];
            }
            min = Math.min(min, sum);
        }
    }
    
    public static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
        if(lx == rx && ly == ry) {
            return;
        }
        
        int[] temp = new int[3]; //방향별로 값을 옮기다 보면 지워질 수 있는 좌표값을 저장.
        temp[0] = copy[lx][ry];
        temp[1] = copy[rx][ry];
        temp[2] = copy[rx][ly];
        
        //오른쪽으로 회전
        for(int i = ry; i > ly; i--) {
            copy[lx][i] = copy[lx][i - 1];
        }
        //아래로 회전
        for(int i = rx; i > lx; i--) {
            if(i == lx + 1) copy[i][ry] = temp[0];
            else copy[i][ry] = copy[i - 1][ry];
        }
        //왼쪽으로 회전
        for(int i = ly; i < ry; i++) {
            if(i == ry - 1) copy[rx][i] = temp[1];
            else copy[rx][i] = copy[rx][i + 1];
        }
        //위로 회전
        for(int i = lx; i < rx; i++) {
            if(i == rx - 1) copy[i][ly] = temp[2];
            else copy[i][ly] = copy[i + 1][ly];
        }    
        rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
    }
}