-
[백준 17406] 배열 돌리기 4Algorithm/Source Code 2022. 8. 14. 22:04반응형
문제
크기가 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와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.
solution.java
package 강수지; import java.io.*; import java.util.*; public class P028_BJ17406_배열돌리기4 { static int N, M, K, min; static int arr[][]; // 원본 배열 static int 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]; // rcs 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); } 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; //r-s int y1 = rotation[numbers[i]][1] - rotation[numbers[i]][2] - 1; //c-s int x2 = rotation[numbers[i]][0] + rotation[numbers[i]][2] - 1; //r+s int y2 = rotation[numbers[i]][1] + rotation[numbers[i]][2] - 1; //c+s 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; } } 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); } // rotate end 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); } } // 각 행의 최소값을 답으로 내기 위해 .. }
출처
https://www.acmicpc.net/problem/17406
반응형'Algorithm > Source Code' 카테고리의 다른 글
[백준 14503] 로봇 청소기 (0) 2022.08.21 알고리즘은 순조부 .. Java로 구현해보자 ! (0) 2022.08.20 [백준 2961] 도영이가 만든 맛있는 음식 (0) 2022.08.11 [백준 16926] 배열 돌리기1 (0) 2022.08.11 [백준 1244] 스위치 켜고 끄기 (0) 2022.08.01