[ 백준 17406 ] 배열 돌리기 4 ( 자바 )

[ 백준 17406 ] 배열 돌리기 4 ( java ) 

 

출처: 백준 코딩 테스트 연습, https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

 

 

 

핵심 

1 dfs를 이용한 회전 순서 설정 

전형적인 dfs 방식으로 orders 배열에 순서를 저장한다. 

orders[i]: i 번째로 회전할 회전 번호 

 

2 회전 

하나의 순서가 완성되면, 문제에서 주어진 대로 회전시키면 된다. 

( y-x, x-s ) 값을 따로 빼두고, 왼쪽, 아래, 오른쪽, 위쪽 변 순서대로 한 칸씩 시계방향으로 이동시킨다. 

마지막으로 따로 빼둔 값을 ( y-x, x-s+1) 로 옮기면 된다. 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        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());
        
        map = new int[N+1][M+1];
        copy = new int[N+1][M+1];
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1 ; j<= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        rots = new int[K][3];
        selected = new boolean[K];
        orders = new int[K];
        int y, x, s;
        for(int i = 0 ; i < K ; i++) {
            st = new StringTokenizer(br.readLine());
            y = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            rots[i][0] = y;
            rots[i][1] = x;
            rots[i][2] = s;
        }
        dfs(0);
        System.out.println(min);
    }
    static int N, M, K;
    static int[][] map, copy;
    static int[][] rots; // rots[i][3] i번호 회전에 대한 정보 
    
    static int[] orders; // orders[i]: i번째로 회전할 회전의 번호 
    static boolean[] selected;
    static int min = Integer.MAX_VALUE;
    static void dfs(int oi) {
        
        if(oi == K) {
            
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j<= M; j++) {
                    copy[i][j] = map[i][j];
                }
            }
            
            int y, x, s;
            for(int oi2 = 0 ; oi2 < K; oi2++) {
                y = rots[orders[oi2]][0];
                x = rots[orders[oi2]][1];
                s = rots[orders[oi2]][2];
                rotate(y, x, s);
            }
            
            int sum;
            for( y = 1 ; y <= N ; y++) {
                sum = 0;
                for( x = 1 ; x <= M; x++) {
                    sum += copy[y][x];
                }
                if(min > sum)
                    min = sum;
            }
            return;
        }
        
        for(int num = 0 ; num < K ; num++) {
            if(!selected[num]) {
                selected[num] = true;
                orders[oi] = num;
                dfs(oi+1);
                selected[num] = false;
            }
        }
    }
    
    static void rotate(int oy, int ox, int os) {
        int sy, sx, ey, ex, start ;
        for(int s = os ; s >= 1; s-- ) {
            sy = oy - s;
            sx = ox - s;
            ey = oy + s;
            ex = ox + s;
            
            start = copy[sy][sx];
            
            for(int y = sy+1 ; y <= ey ; y++) {
                copy[y-1][sx] = copy[y][sx];
            }
            
            for(int x = sx+1 ; x <= ex ; x++) {
                copy[ey][x-1] = copy[ey][x];
            }
            
            for(int y = ey-1; y >= sy ; y--) {
                copy[y+1][ex] = copy[y][ex];
            }
            
            for(int x = ex -1 ; x >= sx+1 ; x--) {
                copy[sy][x+1] = copy[sy][x];
            }
            copy[sy][sx+1] = start;
        }
    }
}