[JAVA][BOJ][G4] 17406. 배열 돌리기 4

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의 값의 최솟값을 출력한다.

풀이

/*
 * 입력
 * 1. 배열의 크기 N, M, 회전 연산의 개수 K
 * 2. 배열
 * 3. 회전 연산의 정보 r, c, s
 * 출력
 * 1. 배열 A의 값의 최솟값
 * 조건
 * 1. 행에 있는 모든 수의 합 중 최솟값
 * 2. r-s, c-s부터 r+s, c+s를 시계 방향으로 한 칸씩 돌림(정사각형)
 * 3. 회전 연산은 임의로 순서를 변경할 수 있음
 * 
 * >> 순열
 */

순열을 이용한다는 생각만 할 수 있으면 간단하지는 않지만 간단하게 풀 수 있다 구현은 항상... 막코딩으로 풀어야 하는데 코딩보다 디버깅에 훨씬 많은 시간을 쏟게 되는 것 같다 특히 배열 문제에서는 인덱스.... 범위.... 쉽게 풀 수 있는 공식이라도 있었으면 좋겠는데 다음에 규칙 찾아서 정리라도 해 봐야겠다

코드

package 구현;

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

public class g4_17406_배열돌리기4 {
	static int N, M, K, min, arr[][], rotation[][];
	static int[] numbers;
	static boolean[] isSelected;
	
	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());
		
		arr = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		rotation = new int[K][3];
		
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				rotation[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		numbers = new int[K];
		isSelected = new boolean[K];
		min = Integer.MAX_VALUE;
		
		Permutation(0);
		
		System.out.println(min);
		
	}

	private static void Permutation(int cnt) {
		if(cnt == K) {
			int[][] tmp = new int[N][M];
			
			for(int i = 0; i<N; i++) {
				for(int j = 0; j<M; j++) {
					tmp[i][j] = arr[i][j];
				}
			}
			
			for(int i = 0; i<K; i++) {
				int x1 = rotation[numbers[i]][0] - rotation[numbers[i]][2] - 1;
				int y1 = rotation[numbers[i]][1] - rotation[numbers[i]][2] - 1;
				int x2 = rotation[numbers[i]][0] + rotation[numbers[i]][2] - 1;
				int y2 = rotation[numbers[i]][1] + rotation[numbers[i]][2] - 1;

				Rotate(x1, y1, x2, y2, tmp);
			}
			
			Min(tmp);
			
			return;
		}
		
		for (int i = 0; i < K; i++) {
			if(isSelected[i]) continue;
			numbers[cnt] = i;
			isSelected[i] = true;
			Permutation(cnt+1);
			isSelected[i] = false;
		}
		
	}

	private static void Rotate(int x1, int y1, int x2, int y2, int[][] tmp) {
        if(x1 == x2 && y1 == y2) {
            return;
        }
        
        int[] ver = new int[3];
        ver[0] = tmp[x1][y2];
        ver[1] = tmp[x2][y2];
        ver[2] = tmp[x2][y1];
        
        for(int i = y2; i > y1; i--) {
            tmp[x1][i] = tmp[x1][i - 1];
        }

        for(int i = x2; i > x1; i--) {
            if(i == x1 + 1) tmp[i][y2] = ver[0];
            else tmp[i][y2] = tmp[i - 1][y2];
        }

        for(int i = y1; i < y2; i++) {
            if(i == y2 - 1) tmp[x2][i] = ver[1];
            else tmp[x2][i] = tmp[x2][i + 1];
        }

        for(int i = x1; i < x2; i++) {
            if(i == x2 - 1) tmp[i][y1] = ver[2];
            else tmp[i][y1] = tmp[i + 1][y1];
        }    
        
        Rotate(x1 + 1, y1 + 1, x2 - 1, y2 - 1, tmp);
    }
	
	private static void Min(int[][] tmp) {
		for(int i = 0; i < N; i++) {
			int sum = 0;
			for(int j = 0; j < M; j++) {
				sum += tmp[i][j];
			}
			
			min = Math.min(min, sum);
		}
	}
}

결과

 

#자바 #java #boj #백준 #알고리즘