[백준] 17406번 배열 돌리기 4 (Java)

0. 출처

백준 17406번 문제입니다.

 

1. 문제

크기가 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의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

(1) 입력

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

(2) 출력

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

 

2. 문제 풀이

(1) 문제 풀이 방법

회전 연산을 모두 한 번씩 사용하되, 순서는 임의로 정해도 되는 것이니 순열을 사용해서 회전 연산의 순서를 정합니다. 회전 연산의 순서를 정한 후에 회전을 수행하고 최솟값을 구하면 됩니다.

static void permutation(int depth, boolean[] visited, int[] result) {
    if(depth == K) {
        getNewArr(); // 1. 회전 배열을 초기화합니다.
        for(int n: result) { // 2. 순서대로 회전을 시킵니다.
            rotate(rotation[n].x1, rotation[n].y1, rotation[n].x2, rotation[n].y2);
        }
        min = Math.min(min, getMin()); // 회전시킨 배열의 최솟값을 구하여 갱신합니다.
        return;
    }

    for(int i=0; i<K; i++) {
        if(!visited[i]) {
            visited[i] = true;
            result[depth] = i;
            permutation(depth+1, visited, result);
            visited[i] = false;
        }
    }
}

 

회전은 시계 방향으로 수행하면 되고, 정사각형으로 범위가 회전하는 것이기 때문에 x1>x2 && y1>y2 조건이 만족할 동안 while문을 돌며 회전을 시키면 됩니다.

 

방법은 간단하지만 코드가 길어 복잡해지기 쉬운 문제죠..

 

(2) 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, K;
    static int[][] A; // 기존 배열
    static int[][] arr; // 회전시킬 배열
    static Rotation[] rotation;
    
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        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());

        A = new int[N+1][M+1];
        arr = new int[N+1][M+1];

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

        rotation = new Rotation[K];
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            rotation[i] = new Rotation(r-s, c-s, r+s, c+s);
        }

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

        System.out.println(min);
        br.close();
    }
    
    // 회전 배열 되돌리기
    static void getNewArr() {
        for(int i=1; i<N+1; i++) {
            for(int j=1; j<M+1; j++) {
                arr[i][j] = A[i][j];
            }
        }
    }
    
    // 회전하기
    static void rotate(int x1, int y1, int x2, int y2) {
        while(x1<x2 && y1<y2) {
            int next = arr[x1][y1];
            int now = 0;

            // 오른쪽
            for(int i=y1+1; i<=y2; i++) {
                now = arr[x1][i];
                arr[x1][i] = next;
                next = now;
            }

            // 아래
            for(int i=x1+1; i<=x2; i++) {
                now = arr[i][y2];
                arr[i][y2] = next;
                next = now;
            }

            // 왼쪽
            for(int i=y2-1; i>=y1; i--) {
                now = arr[x2][i];
                arr[x2][i] = next;
                next = now;
            }

            // 위
            for(int i=x2-1; i>=x1; i--) {
                now = arr[i][y1];
                arr[i][y1] = next;
                next = now;
            }

            x1++;
            y1++;
            x2--;
            y2--;
        }
    }

	// 최솟값 찾기
    static int getMin() {
        int result = Integer.MAX_VALUE;

        for(int i=1; i<arr.length; i++) {
            int count = 0;
            for(int j=1; j<arr[0].length; j++) {
                count += arr[i][j];
            }
            result = Math.min(count, result);
        }

        return result;
    }
    
    // 회전 순서를 결정하는 순열
    static void permutation(int depth, boolean[] visited, int[] result) {
        if(depth == K) {
            getNewArr();
            for(int n: result) {
                rotate(rotation[n].x1, rotation[n].y1, rotation[n].x2, rotation[n].y2);
            }
            min = Math.min(min, getMin());
            return;
        }

        for(int i=0; i<K; i++) {
            if(!visited[i]) {
                visited[i] = true;
                result[depth] = i;
                permutation(depth+1, visited, result);
                visited[i] = false;
            }
        }
    }

    static class Rotation {
        int x1, y1, x2, y2;

        public Rotation(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
    }    
}

 

(3) 결과