[BOJ] 17406 배열돌리기 4 - JAVA

1. 문제

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

17406번: 배열 돌리기 4

---

2. 풀이

static 변수들

static int[][] deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//오른쪽, 아래, 왼쪽, 위
static int N, M, K;	// 배열 크기, 회전 개수
static int[][] A;	//배열
static int MIN = Integer.MAX_VALUE;	//배열의 최소값 저장
static boolean[] isSelected;	//방문여부 저장 배열(회전 순서 정할 때 쓰임)
static int[][] numbers;	//회전 순서 저장 배열
static int[][] turns;	//입력받은 회전 정보 저장 배열

 

배열 깊은복사, 배열 최소값 계산

• 원본 A를 보존해야하기 때문에 깊은 복사가 필요하다.

private static int[][] copyArray(){
    int[][] arr = new int[N][M];
    for(int k=0;k<A.length;k++){
        System.arraycopy(A[k],0,arr[k],0,A[k].length);
    }
    return arr;
}

private static int calcMin(int[][] arr){
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < N; i++) {
        int sum = 0;
        for (int j = 0; j < M; j++) sum += arr[i][j];
        if (min > sum) min = sum;
    }
    return min;
}

 

회전 순서 정하기

• K만큼 반복하면서 이미 선택된 회전이 아니라면 재귀로 방문한다(카운트+1). 방문이 끝나면 isSelected를 되돌려놓는다.
• 카운트가 회전개수K와 동일하면 저장된 순서대로 회전하고, static MIN과 현재의 min을 비교해서 저장한다.
• 회전하는 부분배열은 항상 한 변의 길이가 2*s인 정사각형이므로 회전 한 번 당 s번 만큼 turnArr배열을 호출한다.

private static void permutation(int cnt){
    if(cnt==K){
        //회전 다 하고 최소값비교
        int[][] arr = copyArray();
        for(int k=0;k<K;k++){
            for (int i = 0; ; i++) {
                //s만큼 반복하면 끝
                if (i >= numbers[k][2]) break;

                //회전하기
                arr = turnArr(arr, i, numbers[k][0], numbers[k][1], numbers[k][2]);
            }
        }

        MIN = Math.min(MIN,calcMin(arr));

        return;
    }

    for(int k=0;k<K;k++){
        if(isSelected[k]) continue;
        numbers[cnt] = turns[k];
        isSelected[k] = true;
        permutation(cnt+1);
        isSelected[k] = false;
    }
}

 

배열 회전

• 회전할 배열arr, 몇 번째 껍질(?)인지i, 회전할 부분의 중심 인덱스(r,c), 중심에서 얼마나 멀어져야하는지s를 파라미터로 받는다. 방식은 2022.02.12 - [알고리즘/BOJ] - [BOJ] 16926 배열돌리기1 - JAVA 와 같다. 
• 회전할 부분은 r-s부터 r+s, c-s부터 c+s이므로 i를 더하거나 빼준다. 

private static int[][] turnArr(int[][] arr, int i, int r, int c, int s) {
    int y = r - s + i;
    int x = c - s + i;
    int d = 0;

    int num = arr[y][x];

    while (true) {
        if (d == 4) break;

        int tmpy = y + deltas[d][0];
        int tmpx = x + deltas[d][1];

        if (tmpy < r - s + i|| tmpy > r + s - i|| tmpx < c - s + i|| tmpx > c + s - i) {
            ++d;
            continue;
        }

        int n = num;
        num = arr[tmpy][tmpx];
        arr[tmpy][tmpx] = n;

        y = tmpy;
        x = tmpx;

    }

    return arr;

}

 

메인 함수

public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(in.readLine());

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

    A = new int[N][M];

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

    //회전 정보 저장
    turns = new int[K][3];
    for (int k = 0; k < K; k++) {
        st = new StringTokenizer(in.readLine());
        turns[k][0] = Integer.parseInt(st.nextToken())-1;
        turns[k][1] = Integer.parseInt(st.nextToken())-1;
        turns[k][2] = Integer.parseInt(st.nextToken());
    }

    //순서정하기
    isSelected = new boolean[K];
    numbers = new int[K][3];
    permutation(0);

    //최소값 출력
    System.out.println(MIN);
}

---

3. 결과

2022.02.12 - [알고리즘/BOJ] - [BOJ] 16935 배열돌리기 3 - JAVA처럼 순서대로 회전하면 되는 줄 알았다가 틀렸다. 그 다음에는 s만큼만 반복하면 되는데 r,c값과 비교하느라 배열 범위를 벗어났다. 

문제 자체를 이해하기는 어렵진 않았지만 그걸 구현하는 데 너무 많은 시간이 걸렸다.