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

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

17406번: 배열 돌리기 4

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

예제 입력 1 

5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1

예제 출력 1 

12

---

풀이

1번 우리는 K개의 사이클 입력 정보가 주어진다.

2개라고 가정하면

(0, 1) , (1, 0)의 결과값이 다 다르므로 모든 경우를 다 검사해줘야한다. 이부분은 순열을 통해 찾아주었다.

 

1. 순열을 통한 회전정보 순서 정해주기.

public static void permutation(int cnt, int[] arr, boolean[] visited) {
    if(cnt == K) {
        doCycle(arr);
        return;
    }
    for(int i=0; i<K; i++) {
        if(visited[i]) continue;
        visited[i] = true;
        arr[cnt] = i;
        permutation(cnt+1, arr, visited);
        visited[i] = false;
    }
}

2. 순열로 순서가 정해줬다면 정해진 순서로 배열을 돌리면됩니다.

2-1) 원본 입력값이 변하면 안되기때문에 돌리기 전에 깊은 복사로 새로운 배열을 만들어서 돌려줘야한다.

public static int[][] copyMap() {
    int[][] tmp = new int[N][M];

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            tmp[i][j] = map[i][j];
        }
    }

    return tmp;
}

public static void doCycle(int[] arr) {
    int[][] tmp = copyMap();

    for(int k=0; k<K; k++) {
        int r = cycle[arr[k]][0];
        int c = cycle[arr[k]][1];
        int S = cycle[arr[k]][2];

        for(int s=1; s<=S; s++) {
            //위
            int upTmp = tmp[r-s][c+s];
            for(int y = c+s; y > c-s; y--) {
                tmp[r-s][y] = tmp[r-s][y-1];
            }
            //오른쪽
            int rightTmp = tmp[r+s][c+s];
            for(int x = r+s; x > r-s; x--) {
                tmp[x][c+s] = tmp[x-1][c+s];
            }
            tmp[r-s+1][c+s] = upTmp;
            //아래
            int leftTmp = tmp[r+s][c-s];
            for(int y = c-s; y < c+s; y++) {
                tmp[r+s][y] = tmp[r+s][y+1];
            }
            tmp[r+s][c+s-1] = rightTmp;
            //왼쪽
            for(int x = r-s; x < r+s; x++) {
                tmp[x][c-s] = tmp[x+1][c-s];
            }
            tmp[r+s-1][c-s] = leftTmp;
        }
    }

    getAnswer(tmp);
}

회전하는 함수이다. 함수의 방식은 아래 그림과 같다.

좌상단부터 위, 오른쪽, 아래, 왼쪽 순으로 밀어주었다. 중간중간 체크돼있는 숫자를 tmp로 바꿔주는 작업이 필요하다.

 

3. 회전을 마쳤다면 행의 합을 구해서 최솟값을 탐색합니다.

public static void getAnswer(int[][] tmp) {
    for(int i=0; i<N; i++) {
        int sum = 0;
        for(int j=0; j<M; j++) {
            sum += tmp[i][j];
        }
        if(min > sum) min = sum;
    }
}

 

전체 코드

package 백준;

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

public class BJ_G4_17406_배열돌리기4 {
    static int N, M, K;
    static int[][] cycle;
    static int[][] map;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cycle = new int[K][3];

        for(int k = 0; k<K; k++) {
            st = new StringTokenizer(br.readLine());
            cycle[k][0] = Integer.parseInt(st.nextToken()) - 1;
            cycle[k][1] = Integer.parseInt(st.nextToken()) - 1;
            cycle[k][2] = Integer.parseInt(st.nextToken());
        }

        permutation(0, new int[K], new boolean[K]);

        System.out.printf("%d", min);
    }

    public static void permutation(int cnt, int[] arr, boolean[] visited) {
        if(cnt == K) {
            doCycle(arr);
            return;
        }
        for(int i=0; i<K; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            arr[cnt] = i;
            permutation(cnt+1, arr, visited);
            visited[i] = false;
        }
    }

    public static void doCycle(int[] arr) {
        int[][] tmp = copyMap();

        for(int k=0; k<K; k++) {
            int r = cycle[arr[k]][0];
            int c = cycle[arr[k]][1];
            int S = cycle[arr[k]][2];

            for(int s=1; s<=S; s++) {
                //위
                int upTmp = tmp[r-s][c+s];
                for(int y = c+s; y > c-s; y--) {
                    tmp[r-s][y] = tmp[r-s][y-1];
                }
                //오른쪽
                int rightTmp = tmp[r+s][c+s];
                for(int x = r+s; x > r-s; x--) {
                    tmp[x][c+s] = tmp[x-1][c+s];
                }
                tmp[r-s+1][c+s] = upTmp;
                //아래
                int leftTmp = tmp[r+s][c-s];
                for(int y = c-s; y < c+s; y++) {
                    tmp[r+s][y] = tmp[r+s][y+1];
                }
                tmp[r+s][c+s-1] = rightTmp;
                //왼쪽
                for(int x = r-s; x < r+s; x++) {
                    tmp[x][c-s] = tmp[x+1][c-s];
                }
                tmp[r+s-1][c-s] = leftTmp;
            }
        }

        getAnswer(tmp);
    }

    public static int[][] copyMap() {
        int[][] tmp = new int[N][M];

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                tmp[i][j] = map[i][j];
            }
        }

        return tmp;
    }

    public static void getAnswer(int[][] tmp) {
        for(int i=0; i<N; i++) {
            int sum = 0;
            for(int j=0; j<M; j++) {
                sum += tmp[i][j];
            }
            if(min > sum) min = sum;
        }
    }
}