(알고리즘) 백준 17406 java 자바

원종식·2022년 8월 3일

문제

백준 17406 배열 돌리기 4 : https://www.acmicpc.net/problem/17406

크기가 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의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

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

제한

3 ≤ N, M ≤ 50
1 ≤ K ≤ 6
1 ≤ A[i][j] ≤ 100
1 ≤ s
1 ≤ r-s < r < r+s ≤ N
1 ≤ c-s < c < c+s ≤ M

예제 입력 1

5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1

예제 출력 1

풀이

이 문제는 풀이라고 할게 없다. 그냥 미친듯이 빡 구현!
먼저 주어진 회전의 가능한 순서들의 순열을 만든다. 각 순열대로 회전을 시킨 후 해당 케이스의 배열값을 구해서 최소값과 비교해서 저장해준다.
나는 로테이트를 재귀적으로 풀었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ17406 {
    static int Y;
    static int X;
    static int C;
    static int[][] origin;
    static int[][] map;
    static int[][] order;
    static int order2[];
    static int used[];
    static int ans=Integer.MAX_VALUE;
    
    public static int getAns(){//최종 형태에서 배열 값 구하는 함수
        int ret=Integer.MAX_VALUE;
        for(int i=0;i<Y;i++){
            int temp=0;
            for(int j=0;j<X;j++){
                temp+=map[i][j];
            }
            if(temp<ret){
                ret=temp;
            }
        }
        return ret;
    }
    public static void mkOrder(int d){//순열 만드는 함수
        if(d==order2.length){//순열이 완성되면
            for(int i=0;i<Y;i++){
                for(int j=0;j<X;j++){
                    map[i][j]=origin[i][j];
                }
            }
            for(int i=0;i<d;i++){//순열대로
                //배열을 회전시킨다(order2가 순열)
                rotate(order[order2[i]][0]-order[order2[i]][2]-1,order[order2[i]][1]-order[order2[i]][2]-1,order[order2[i]][0]+order[order2[i]][2]-1,order[order2[i]][1]+order[order2[i]][2]-1);
            }
            int t=getAns();
            if(ans>t){
                ans=t;
            }
        }
        for(int i=0;i<C;i++){//순열 만들기
            if(used[i]==0){
                order2[d]=i;
                used[i]=1;
                mkOrder(d+1);
                used[i]=0;
            }
        }

    }
    public static void rotate(int sY,int sX,int eY,int eX){//회전시키기
        if(sX>eX){
            return;
        }
        int arr[]=new int[4*(eX-sX)];//순서대로 쫙 넣어줄 변수
        int p=0;
        //순서대로 쫙 넣어준 다음에
        for(int i=sX;i<eX;i++){
            arr[p++]=map[sY][i];
        }
        for(int i=sY;i<eY;i++){
            arr[p++]=map[i][eX];
        }
        for(int i=eX;i>sX;i--){
            arr[p++]=map[eY][i];
        }
        for(int i=eY;i>sY;i--){
            arr[p++]=map[i][sX];
        }
        //한칸씩 미뤄서 순서대로 쭉 뺴준다
        p=0;
        for(int i=sX+1;i<=eX;i++){
            map[sY][i]=arr[p++];
        }
        for(int i=sY+1;i<=eY;i++){
            map[i][eX]=arr[p++];
        }
        for(int i=eX-1;i>=sX;i--){
            map[eY][i]=arr[p++];
        }
        for(int i=eY-1;i>=sY;i--){
            map[i][sX]=arr[p++];
        }
        rotate(sY+1, sX+1, eY-1, eX-1);
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        Y=Integer.parseInt(st.nextToken());
        X=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        map=new int[Y][X];
        origin=new int[Y][X];

        for(int i=0;i<Y;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<X;j++){
                origin[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        order=new int[C][3];
        order2=new int[C];
        used=new int[C];
        for(int i=0;i<C;i++){
            st=new StringTokenizer(br.readLine());
            order[i][0]=Integer.parseInt(st.nextToken());
            order[i][1]=Integer.parseInt(st.nextToken());
            order[i][2]=Integer.parseInt(st.nextToken());
        }
        mkOrder(0);
        System.out.println(ans);
    }
}