Life Engineering
[BOJ 17406] 배열 돌리기 4 (Java) 본문
https://www.acmicpc.net/problem/17406
import java.util.Arrays;
import java.util.Scanner;
public class P17406 {
static int N, M, K;
static int[][] A;
static int[][] temp;
static Rotate[] rotates;
static Rotate[] orders;
static boolean[] check;
static int answer=Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int r,c,s;
N=sc.nextInt();
M=sc.nextInt();
K=sc.nextInt();
A=new int[N+1][M+1];
temp=new int[N+1][M+1];
rotates=new Rotate[K];
orders=new Rotate[K];
check=new boolean[K];
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
A[i][j]=sc.nextInt();
temp[i][j]=A[i][j];
}
}
for (int i=0; i<K; i++) {
r=sc.nextInt();
c=sc.nextInt();
s=sc.nextInt();
rotates[i]=new Rotate(r,c,s);
}
perm(0);
System.out.println(answer);
}
private static void perm(int cnt) {
if (cnt==K) {
for (int i=1; i<=N; i++) {
for (int j=1; j<=M; j++) {
A[i][j]=temp[i][j];
}
}
for (int i=0; i<K; i++) {
clock(orders[i]);
}
answer=Math.min(answer, calc());
return;
}
for (int i=0; i<K; i++) {
if (check[i]) {
continue;
}
check[i]=true;
orders[cnt]=rotates[i];
perm(cnt+1);
check[i]=false;
}
}
private static int calc() {
int[] sums=new int[N+1];
int min=Integer.MAX_VALUE;
for (int i=1; i<=N; i++) {
int tot=0;
for (int j=1; j<=M; j++) {
tot+=A[i][j];
}
sums[i]=tot;
}
for (int i=1; i<=N; i++) {
min=Math.min(min, sums[i]);
}
return min;
}
private static void clock(Rotate ro) {
for (int i=ro.s; i>=0; i--) {
clock2(ro.r-i, ro.c-i, ro.r+i, ro.c+i);
}
}
private static void clock2(int sr, int sc, int er, int ec) {
int now_r, now_c;
int temp=A[sr][sc];
now_r=sr;
while (now_r<er) {
A[now_r][sc]=A[now_r+1][sc];
now_r++;
}
now_c=sc;
while (now_c<ec) {
A[er][now_c]=A[er][now_c+1];
now_c++;
}
while (now_r>sr) {
A[now_r][ec]=A[now_r-1][ec];
now_r--;
}
while (now_c>sc) {
A[sr][now_c]=A[sr][now_c-1];
now_c--;
}
if (!(sr==er && sc==ec)) {
A[sr][sc+1]=temp;
}
}
public static class Rotate{
int r,c,s;
Rotate(int r, int c, int s) {
this.r = r;
this.c = c;
this.s = s;
}
}
}
순열로 가능한 수를 만들어서 배열을 돌려주는 문제이다.
배열을 돌려줄 때, s를 기반으로 테두리를 회전하는 방식을 취했다. s가 0이 될때까지 감소시켜주면서, 그에 해당하는 테두리의 값들을 이동시켜준다.
여기서 주의할점은 (start row , start col) 의 바로 오른쪽 옆 칸에 기존에 저장했던 (start row , start col) 의 값을 넣어줘야 한다는 것이다.
시계 반대방향으로 값을 읽어와서 저장하는 방식을 취하면 된다.
'Problem Solving' 카테고리의 다른 글
[SW Expert 1234] 비밀번호 (Java) (0) | 2022.02.09 |
---|---|
[BOJ 2493] 탑 (Java) (0) | 2022.02.07 |
[BOJ 19237] 어른 상어 (Java) (0) | 2022.02.05 |
[SW Expert 1210] Ladder1 (Java) (0) | 2022.02.04 |
[프로그래머스] k진수에서 소수 개수 구하기 (Java) (0) | 2022.01.31 |